Merge LinkedList - Why does this code caused an infinite loop?-CodePudding

I am attempting leetcode merging of sorted linkedlist

I have just discovered a mistake of my code that I placed list1 = list1.next right before the result.next = list1, causing the code to caused an infinite loop. However, I tried to trace and still don't understand how the logic caused an infinite loop.

Wrong Solution

    // Loop until list1 and list2 is not empty
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            list1 = list1.next;
            result.next = list1;
            
        } else {
            list2 = list2.next;
            result.next = list2;
            
        }

        System.out.println(list2.val);

        result = result.next;

    }

Correct Solution

    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            
            result.next = list1;
            list1 = list1.next;
            
        } else {
            
            result.next = list2;
            list2 = list2.next;
            
        }

        System.out.println(list2.val);

        result = result.next;

    }

Can someone enlighten me why does the placement of list1 = list1.next and list2 = list2.next, will caused an infinite loop? Here are my debugging attempts

As you can see the two images, represents the value of the result linkedlist, which will continuously loop through the value of 4,2,3 -> 2,4,2 -> 4,2,3 -> 2,4,2 .... vice versa.

Finally here is my input 1,2,4 1,3,4

CodePudding user response：

When you draw the states of your list nodes on a piece of paper step by step, you'll see how that cycle gets introduced.

Here is a visualisation -- step by step. I assume the code has first created a dummy node to which also result has a reference. Before the loop gets executed we thus have this state:

list1
  ↓ 
┌───┐   ┌───┐   ┌───┐
│ 1 ├──►│ 2 ├──►│ 4 ├──► null
└───┘   └───┘   └───┘

list2
  ↓ 
┌───┐   ┌───┐   ┌───┐
│ 1 ├──►│ 3 ├──►│ 4 ├──► null
└───┘   └───┘   └───┘

result
  ↓ 
┌───┐
│   ├──► null
└───┘
  ↑
dummy

Iteration 1 of the loop: if condition is false, so list2 is moved, and then result->next gets the same reference, and then result itself moves:

list1
  ↓ 
┌───┐   ┌───┐   ┌───┐
│ 1 ├──►│ 2 ├──►│ 4 ├──► null
└───┘   └───┘   └───┘

        list2
          ↓ 
┌───┐   ┌───┐   ┌───┐
│ 1 ├──►│ 3 ├──►│ 4 ├──► null
└───┘┌─►└───┘   └───┘
     │    ↑
┌───┐│  result
│   ├┘
└───┘
  ↑
dummy

Iteration 2 of the loop: if condition is true, so list1 is moved, and then result->next gets the same reference, and then result itself moves:

        list1
          ↓ 
┌───┐   ┌───┐   ┌───┐
│ 1 ├──►│ 2 ├──►│ 4 ├──► null
└───┘┌─►└───┘   └───┘
     │    ↑
     │  result
     └───────┐
        list2│
          ↓  │
┌───┐   ┌───┐│  ┌───┐
│ 1 ├──►│ 3 ├┘  │ 4 ├──► null
└───┘┌─►└───┘   └───┘
     │    
┌───┐│
│   ├┘
└───┘
  ↑
dummy

At this point we already have a serious problem, as the last node that belonged to the second list has now become detached and unreachable.

Iteration 3 of the loop: if condition is true, so list1 is moved, and then result->next gets the same reference (but this was already the case), and then result itself moves:

                list1
                  ↓ 
┌───┐   ┌───┐   ┌───┐
│ 1 ├──►│ 2 ├──►│ 4 ├──► null
└───┘┌─►└───┘   └───┘
     │            ↑
     │          result
     └───────┐
        list2│
          ↓  │
┌───┐   ┌───┐│  ┌───┐
│ 1 ├──►│ 3 ├┘  │ 4 ├──► null
└───┘┌─►└───┘   └───┘
     │    
┌───┐│
│   ├┘
└───┘
  ↑
dummy

Iteration 4 of the loop: if condition is false, so list2 is moved (and is going the wrong way!), and then result->next gets the same reference (creating the cycle!), and then result itself moves:

        list2   list1
          ↓       ↓ 
     ┌───────────────┐
┌───┐└─►┌───┐   ┌───┐│
│ 1 ├──►│ 2 ├──►│ 4 ├┘
└───┘┌─►└───┘   └───┘
     │    ↑
     │  result
     └───────┐
┌───┐   ┌───┐│  ┌───┐
│ 1 ├──►│ 3 ├┘  │ 4 ├──► null
└───┘┌─►└───┘   └───┘
     │    
┌───┐│
│   ├┘
└───┘
  ↑
dummy

And now the cycle has been made! The node with value 2 points to the node with value 4, and vice versa!

CodePudding user response：

Need to see all the relevent code file before answering,but i observe that you are doing

System.out.println(list2.val);

You are assuming list2!=null here

while (list1 != null && list2 != null)

but in the code you are doing

list2 = list2.next;
            
        }

        System.out.println(list2.val);

what if list2 becomes null here .Need to put null checks