Add two Numbers(Using ListNode)

Question

Given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list

public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode();
        int car = 0;

        while (l1 != null && l2 != null) {
            if (l1.next == null && l2.next != null) {
                l3.val = (l2.val +l1.val+ car) % 10;
                car = (l2.val+l1.val + car) / 10;
                l2 = l2.next;

            } else if (l2.next == null && l1.next != null) {
                l3.val = (l1.val +l2.val+ car) % 10;
                car = (l1.val +l2.val+ car) /10;
                l1 = l1.next;

            } else {
                l3.val = (l1.val + l2.val + car) % 10;
               car = (l1.val + l2.val + car) / 10;

                l1 = l1.next;
                l2 = l2.next;
                if (l1 != null || l2 != null) {
                    l3.next = new ListNode();
                    l3 = l3.next;
                }
                if (l1 == null && l2 == null && car != 0) {
                    l3.next = new ListNode(car);
                    l3 = l3.next;
                }
            }
        }
        return l3;
    }


    public static void main(String[] args) {
        ListNode ll = new ListNode(1);
        ll.next = new ListNode(1);
        //ll.next.next = new ListNode(3);
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(1);
        ListNode l3 = addTwoNumbers(ll, l2);
        ListNode temp = l3;
        while (temp != null) {
            System.out.print(temp.val+"." );
            temp = temp.next;

        }
    }
}

Here I noticed only one node of l3 where there must be two ListNodes with their l3.val= 2 here second ListNode itself not created for l3 ,but as I saw while debugging the loop runs two times..explain me how..?

Answer 1

The main problem is that your l3 reference moves along the newly created linked list, but thereby you lose the reference to the first node of that linked list. With return l3 you always return the last node of that linked list, which then is a list with just one node.

There are some other issues in your code also:

• If l1 and l2 are not of equal length the loop will use the value of the last node in the shortest list multiple times, and the same l3.val is overwritten, leading to wrong results. In other words, as soon as l1.val is used in a sum, l1 = l1.next must be executed to avoid double counting.

• A new node is always created ahead of the next iteration of the loop, which makes the logic overly complex.

Proposed code:

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(); // This is a dummy node
        ListNode tail = l3; // l3 will not move, but tail will.
        int car = 0;

        while (l1 != null || l2 != null || car > 0) { // Work to do?
            // Avoid code repetition and deal with all cases together
            int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + car;
            // Leave l3 at the root, and only move tail
            tail = tail.next = new ListNode(sum % 10);
            car = sum / 10;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return l3.next; // Skip first dummy node
    }

Here the initial node that is created for l3 is not actually used to store a meaningful value. For every meaningful value a new node is created on-the-spot and at the end the dummy node is skipped in the returned linked list.