I'm trying to add 2 linked lists and my code is ending up in an infinite loop. If I replace 5th line by l2.next = addTwoNumbers(l2.next, l1); getting required output but still wanted to know why the below code ends in infinite loop. Please help.

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

Output: 5->9->9->->...goes on like this but expected is 5->9>Null.

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;

}

}

CodePudding user response：

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;
   }