Skip to content
Advertisement

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:

JavaScript

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 5th line by

JavaScript

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

Advertisement

Answer

The problem is in this part of your code:

JavaScript

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:

JavaScript

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

JavaScript

Other remarks

  1. You have:

    JavaScript

    But that should probably just be:

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

    JavaScript
User contributions licensed under: CC BY-SA
3 People found this is helpful
Advertisement