leetcode JavaScript Merge Two Sorted Lists

Question

I wonder why my code got timeout,when I sove that problem in leetcode,I think its the condition of the while-loop that cause it, but could somebody please tell me why? I try to use chatGPT but it cannot give a exact answer.

I think it may be because I made an endless loop. I saw the answers of others and find that they use the ListNode itself in the condition and content of while-loop, and I use ListNode.next,I understand their method, but still have no idea why my method does not work.

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  if (!list1) return list2;
  if (!list2) return list1;
  const dummy = new ListNode(0);
  let l = dummy;
  let l1 = new ListNode(0);
  let l2 = new ListNode(0);
  l1.next = list1;
  l2.next = list2;
  while (l1.next && l2.next) {
    if (l1.next.val < l2.next.val) {
      l.next = l1.next;
      l1 = l1.next;
    } else {
      l.next = l2.next;
      l2 = l2.next;
    }
    l = l.next;
  }
  if (!l1.next) l.next = l2.next;
  if (!l2.next) l.next = l1.next;
  return dummy.next;
};

Answer 1

Let's take an example input of:

list1 = [1, 3]
list2 = [2, 4]

We can visualise the state when the loop is about to start. At that time three dummy nodes have been created, referenced by dummy (and l), l1 and l2:

dummy  l
  ↓    ↓
┌────────────┐
│ val: 0     │
│ next: null │
└────────────┘
      l1             list1     
      ↓                ↓      
    ┌────────────┐   ┌────────────┐   ┌────────────┐
    │ val: 0     │   │ val: 1     │   │ val: 3     │
    │ next: ────────►│ next: ────────►│ next: null │
    └────────────┘   └────────────┘   └────────────┘

    ┌────────────┐   ┌────────────┐   ┌────────────┐
    │ val: 0     │   │ val: 2     │   │ val: 4     │
    │ next: ────────►│ next: ────────►│ next: null │
    └────────────┘   └────────────┘   └────────────┘
      ↑                ↑
      l2             list2

Iteration 1

In the first iteration the if condition is true, after the two assignments in the if block and the final l = l.next have executed, we have this:

dummy
  ↓
┌────────────┐
│ val: 0     │
│ next: ──────────┐
└────────────┘    │
                  │  list1  l1  l
                  │    ↓    ↓   ↓ 
    ┌────────────┐│  ┌────────────┐   ┌────────────┐
    │ val: 0     │└─►│ val: 1     │   │ val: 3     │
    │ next: ────────►│ next: ────────►│ next: null │
    └────────────┘   └────────────┘   └────────────┘

    ┌────────────┐   ┌────────────┐   ┌────────────┐
    │ val: 0     │   │ val: 2     │   │ val: 4     │
    │ next: ────────►│ next: ────────►│ next: null │
    └────────────┘   └────────────┘   └────────────┘
      ↑                ↑
      l2             list2

The second dummy node (the one that was initially referenced by l1) no longer has a reference, so it can be garbage collected. No problem.

Iteration 2

In the second iteration, we compare 3 with 2, and so the else block is executed. When its two assignments and the final l = l.next have executed, we get:

dummy
  ↓
┌────────────┐
│ val: 0     │
│ next: ──────────┐
└────────────┘    │
                  │  list1  l1
                  │    ↓    ↓ 
                  │  ┌────────────┐   ┌────────────┐
                  └─►│ val: 1     │   │ val: 3     │
                     │ next: ──┐  │   │ next: null │
                     └─────────│──┘   └────────────┘
                  ┌────────────┘
    ┌────────────┐│  ┌────────────┐   ┌────────────┐
    │ val: 0     │└─►│ val: 2     │   │ val: 4     │
    │ next: ────────►│ next: ────────►│ next: null │
    └────────────┘   └────────────┘   └────────────┘
                       ↑    ↑   ↑  
                     list2  l2  l

Here we see a first problem: the node with value 3 has become orphaned! There is no more reference to it, and so it is for ever lost (it can be garbage collected). In the next iteration we can omit another dummy node (originally referrenced by l2) as well. But the problems will mount up...

Iteration 3

In this iteration we no longer have the node with value 3. The comparison is now between 2 and 4, and so the if block executes. The first of the statements in the if block creates a loop: l.next = l1.next because l1.next is the same as l. We can stop the analysis there, because this loop will cause the variables l, l1 and l2 to get stuck in that loop:

dummy
  ↓
┌────────────┐
│ val: 0     │
│ next: ──────────┐
└────────────┘    │
                  │  list1  l1
                  │    ↓    ↓ 
                  │  ┌────────────┐
                  └─►│ val: 1     │
                     │ next: ──┐  │
                     └─────────│──┘
                  ┌────────────┘
                  │  ┌────────────┐   ┌────────────┐
                  └─►│ val: 2     │◄─┐│ val: 4     │
                     │ next: ────────┘│ next: null │
                     └────────────┘   └────────────┘
                       ↑    ↑   ↑  
                     list2  l2  l

The main problem in your code is that you don't keep l1 and l2 ahead of the already merged part of the list. The correct way to do it is to have l1 and l2 reference the two input lists that are still unaltered (not merged), and l should reference the tail of the merged part. So what we see above, where l1 and l2 reference nodes of the same list, should never happen.

As you already know about the correct code, I will leave it at that. I hope it clarifies what went wrong.