Adding two linked list ends in Infinite Loop

I’m trying to solve LeetCode problem 2. Add Two Numbers:

You are 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

My code is ending up in an infinite loop:

private static Node addTwoNumbers(Node l1, Node l2) {
    if (l1 == null && l2 == null)
        return l1;
    if (l1 == null) {
        l2.next = addTwoNumbers(l2, l1);
        return l2;
    }
    if (l2 == null) {
        if (l1.data > 9) {
            if (l1.next != null) {
                l1.next.data = l1.next.data + 1;
            } else
                l1.next = new addLinkedList().new Node(1);

            l1.data = (l1.data) % 10;
        }
        l1.next = addTwoNumbers(l1.next, l2);
        return l1;

    }

    if (l1.data + l2.data > 9) {
        l1.data = (l1.data + l2.data) % 10;
        if (l1.next != null) {
            l1.next.data = l1.next.data + 1;
        } else
            l1.next = new addLinkedList().new Node(1);

    } else {
        l1.data = l1.data + l2.data;

    }
    l1.next = addTwoNumbers(l1.next, l2.next);
    return l1;

}

Input: L1=0->null L2=5->9->null

Expected output: 5->9>null

My Output: 5->9->9->9->... It goes on like this.

If I replace the 5^th line by

l2.next = addTwoNumbers(l2.next, l1);

…then I’m getting the required output, but I still wanted to know why the below code ends in infinite loop.

Answer

The problem is in this part of your code:

    if (l1 == null) {
        l2.next = addTwoNumbers(l2, l1);
        return l2;
    }

The idea behind this case is that you swap l1 and l2 so that you can deal with the single null case without code repetition. That is good, but it is not implemented correctly.

addTwoNumbers(l2, l1) — which is addTwoNumbers(l2, null) in this case — will return l2. But then this return value is assigned to l2.next, i.e. it performs l2.next = l2. That is a cycle! The original l2.next referenced the next node, but now the reference to that next node is lost, and instead we have a list with a loop in it.

It is then not your code that gets into an infinite loop, but the code that calls your function and then verifies the resulting list by iterating it. It is that code that will get into an infinite loop.

You propose yourself a valid correction:

        l2.next = addTwoNumbers(l2.next, l1);
        return l2;

You might also consider just swapping without stepping to the next node:

        return addTwoNumbers(l2, l1);

Other remarks

1. You have:

   l1.next = new addLinkedList().new Node(1);
   

   But that should probably just be:

   l1.next = new Node(1);
   

2. You still have some code repetition. You could avoid that by introducing the add variable as done below:

   private static Node addTwoNumbers(Node l1, Node l2) {
       if (l1 == null) {
           if (l2 == null) {
               return null;
           }
           return addTwoNumbers(l2, l1);
       }
       int add = l2 == null ? 0 : l2.data;
       if (l1.data + add > 9) {
           if (l1.next != null) {
               l1.next.data++;
           } else {
               l1.next = new Node(1);
           }
       }
       l1.data = (l1.data + add) % 10;
       l1.next = addTwoNumbers(l1.next, l2 == null ? null : l2.next);
       return l1;
   }