Error in Adding Two Numbers (digits in linked list)

Question

This is regarding the question on https://oj.leetcode.com/problems/add-two-numbers/

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

The logic I'm following is that I assume list1 to be longer than list2, else swap them. Then, I make the length of list2 equal to list1 by adding nodes containing zeroes at the end of list2. (The code then prints both the lists at this point to check if there has been a mistake yet). After this, I start traversing the lists from the beginning, adding individual digits, overwriting the values in linked list 1 with the sum of digits modulo 10. The carry value is also noted. This is done till the end of the lists. If the carry value is not zero at the very end, a new node is created which contains the carry value, and it is inserted at the end of linked list 1. The head of linked list 1 is returned.

The code works properly in all cases except the one in which a new node has to be added at the very end with the carry value. I print linked list 1 before returning the value, and it is correct at that point. However, returning the head, and printing it in the main function gives a wrong answer with garbage values in the node which was supposed to contain the carry digit. It is almost like that the node with carry digit is replaced by 2-3 nodes with garbage values. Could someone please explain this?

Another issue I observed that is while printing the final ans, if I use cout << ans->val << " " << endl the code terminates properly (returns 0) but prints an incorrect output. If I remove the endl , i.e. use cout << ans->val << " " then the code termminates by throwing up a runtime error (seg fault). I couldn't think of a suitable reason for this.

Thank you for your time and help.

#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
      ListNode* l1_mover = l1;
      ListNode* l2_mover = l2;
      while ((l1_mover->next != NULL) && (l2_mover->next != NULL))
      {
        l1_mover = l1_mover->next;
        l2_mover = l2_mover->next;
      }
      if ((l1_mover->next == NULL) && (l2_mover->next != NULL))
      {
        // Call the function after swapping the lists if the first one is smaller
        cout << "calling function with swapped lists " << endl;
        return addTwoNumbers(l2, l1);
      }
      while (l1_mover->next != NULL)
      {
        ListNode emp(0);
        l2_mover->next = &emp;
        l1_mover = l1_mover->next;
      }
      // Till now, I have equated the lengths of both the lists, by padding the shorter one with zeros.

      cout << "printing list 1 inside. " << endl;
      l1_mover = l1;
      while (l1_mover != NULL)
      {
        cout << l1_mover->val << " ";
        l1_mover = l1_mover->next;
      }
      cout << endl;

      cout << "printing list 2 inside. " << endl;
      l2_mover = l2;
      while (l2_mover != NULL)
      {
        cout << l2_mover->val << " ";
        l2_mover = l2_mover->next;
      }
      cout << endl;
      // The above two print statements show that the lists are still correct
      l1_mover = l1;
      l2_mover = l2;
      int carry = 0;
      while (l1_mover != NULL)
      {
        int digit_sum = l1_mover->val + l2_mover->val + carry;
        carry = digit_sum / 10;
        l1_mover->val = digit_sum % 10;
        //cout << "sum is " << digit_sum << " and l2 val is " << l2_mover->val << endl;
        if (l1_mover->next == NULL)
          break;
        // the above break is so that l1 is not NULL at end of loop.
        l1_mover = l1_mover->next;
        l2_mover = l2_mover->next;
      }
      if (carry != 0)
      {
        cout << "carry not zero " << carry  << endl;
        ListNode last_one(carry);
        l1_mover->next = &(last_one);
      }
      cout << endl << "printing ans inside. " << endl;
      l1_mover = l1;
      while (l1_mover != NULL)
      {
        cout << l1_mover->val << " ";
        l1_mover = l1_mover->next;
      }
      cout << endl << endl;
      // The above lines print the linked list containing the sum. It is observed to be correct.
      return l1;
    }
};

int main()
{
  ListNode a1(8);
  ListNode b1(7);
  ListNode b2(9);
  b1.next = &b2;
  Solution object;
  ListNode* ans = object.addTwoNumbers(&a1, &b1);
  cout << "printing ans " << endl;
  while (ans != NULL)
  {
    cout << ans->val << " " << endl;
    // cout << ans->val << " "; // if this line is used, instead of the above one,
    // the program terminates with an error message. It doesn't give an error if the other line
    // is used.
    ans = ans->next;
  }
}

Answer 1

ListNode last_one(carry);
l1_mover->next = &(last_one);

and you then return l1 ; while last node is local

EDIT : I changed that and works perfectly now, but I only pointed out the problem only, if you want solution too just tell me and I'll had

void print( ListNode * l )
{
    if( l )
    {
        print( l->next ) ;
        cout << l->val ;
    }
}

Answer 2

Why not just read each linked list, extract their intended values, perform the operation (addition), and then re-encode it into a linked list?

The linked lists are already sorted in reverse, which makes the logic easier for adding additional places.

i.e. If you were to conceptualize the linked list as an array...

(linked_list[0] * 1) + (linked_list[1] * 10) + (linked_list[2] * 100)

and so on and so forth.

Then, you add them together, and, since they're both integers, we can use modulo and re-encode:

sum = linked_list_num_1 + linked_list_num_2;

int n = 0;

while (sum != 0)
{ 
    result_linked_list[n] = sum % 10;
    sum = sum / 10;
    ++n;
}

I'm doing linked list containers in my own class right now, and it appears that you could write a lightweight container for the list so that you can at least add and extract nodes with ease.