leecode21, Merge Two Sorted lists

Question

I'm trying to understand the dummy node outputNode and tail node here.

I just have one more question, after declaring the outputNode and tail, there is no interaction between them during the whole process, then how does the final result appear in outputNode.next?

Thanks a million

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode outputNode = new ListNode(0);
        ListNode tail= outputNode;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                tail.next = list1;
                list1 = list1.next;
            }else{
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        if(list1 == null&& list2 != null){
            tail.next = list2;
            list2 = list2.next;
             
        }
        if(list1 != null&& list2 == null){
            tail.next = list1;
            list1 = list1.next;
           
        }
        return outputNode.next;
                
    }
}

Answer 1

It may help to visualise the process. Let's say we merge two lists with values 1, 4 and 2, 3 respectively:

Once the first two statements before the loop are executed, we have tail and outputNode referencing the same "dummy" node:

tail
outputNode
  ↓
┌───────────┐
│ data: 0   │
│ next:null │
└───────────┘

list1
  ↓
┌───────────┐   ┌───────────┐
│ data: 1   │   │ data: 4   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘

┌───────────┐   ┌───────────┐
│ data: 2   │   │ data: 3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑
list2

In the first iteration of the loop, the first if condition is true, and so tail.next = list1 gets executed. This leads to the following:

tail
outputNode
  ↓
┌───────────┐
│ data: 0   │
│ next: ─┐  │
└────────│──┘
         │
list1    │ 
  ↓      ▼
┌───────────┐   ┌───────────┐
│ data: 1   │   │ data: 4   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘

┌───────────┐   ┌───────────┐
│ data: 2   │   │ data: 3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑
list2

Note how it doesn't matter whether you look at it via outputNode or via tail, either way you get to the node that now has a next member that points to the first node of list1.

The next statement assigns a different node reference to list1 with list1 = list1.next:

tail
outputNode
  ↓
┌───────────┐
│ data: 0   │
│ next: ─┐  │
└────────│──┘
         │
         │      list1
         ▼        ↓
┌───────────┐   ┌───────────┐
│ data: 1   │   │ data: 4   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘

┌───────────┐   ┌───────────┐
│ data: 2   │   │ data: 3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑
list2

The last statement in the first iteration of the loop, moves the tail reference, with tail = tail.next:

outputNode
  ↓
┌───────────┐
│ data: 0   │
│ next: ─┐  │
└────────│──┘
         │
tail     │      list1
  ↓      ▼        ↓
┌───────────┐   ┌───────────┐
│ data: 1   │   │ data: 4   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘

┌───────────┐   ┌───────────┐
│ data: 2   │   │ data: 3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑
list2

In the second iteration of the loop, we get into the else block, and there we set tail.next = list2:

outputNode
  ↓
┌───────────┐
│ data: 0   │
│ next: ─┐  │
└────────│──┘
         │
tail     │      list1
  ↓      ▼        ↓
┌───────────┐   ┌───────────┐
│ data: 1   │   │ data: 4   │
│ next: ─┐  │   │ next:null │
└────────│──┘   └───────────┘
         ▼
┌───────────┐   ┌───────────┐
│ data: 2   │   │ data: 3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑
list2

Then list1 = list1.next will lead to:

outputNode
  ↓
┌───────────┐
│ data: 0   │
│ next: ─┐  │
└────────│──┘
         │
tail     │      list1
  ↓      ▼        ↓
┌───────────┐   ┌───────────┐
│ data: 1   │   │ data: 4   │
│ next: ─┐  │   │ next:null │
└────────│──┘   └───────────┘
         ▼
┌───────────┐   ┌───────────┐
│ data: 2   │   │ data: 3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
                  ↑
                 list2

And again, the final statement of this second iteration, will move tail:

outputNode
  ↓
┌───────────┐
│ data: 0   │
│ next: ─┐  │
└────────│──┘
         │
         │      list1
         ▼        ↓
┌───────────┐   ┌───────────┐
│ data: 1   │   │ data: 4   │
│ next: ─┐  │   │ next:null │
└────────│──┘   └───────────┘
         ▼
┌───────────┐   ┌───────────┐
│ data: 2   │   │ data: 3   │
│ next: ──────► │ next:null │
└───────────┘   └───────────┘
  ↑               ↑
tail            list2

And then the third iteration will deliver this state:

outputNode
  ↓
┌───────────┐
│ data: 0   │
│ next: ─┐  │
└────────│──┘
         │
         │      list1
         ▼        ↓
┌───────────┐   ┌───────────┐
│ data: 1   │   │ data: 4   │
│ next: ─┐  │   │ next:null │
└────────│──┘   └───────────┘
         ▼
┌───────────┐   ┌───────────┐
│ data: 2   │   │ data: 3   │
│ next: ──────► │ next: null│
└───────────┘   └───────────┘
                  ↑        
                tail       list2 == null

The part after the loop, will do tail.next = list1 in the last if block. The assignment to list2 really is not needed anymore. The final state is:

outputNode
  ↓
┌───────────┐
│ data: 0   │
│ next: ─┐  │
└────────│──┘
         │
         │                 list1 == null
         ▼
┌───────────┐   ┌───────────┐
│ data: 1   │   │ data: 4   │
│ next: ─┐  │   │ next:null │
└────────│──┘   └───────────┘
         ▼                ▲
┌───────────┐   ┌─────────│─┐
│ data: 2   │   │ data: 3 │ │
│ next: ──────► │ next: ──┘ │
└───────────┘   └───────────┘
                  ↑        
                tail       list2 == null

The return value is outputNode.next, which indeed is the reference to the first node of the merged list.

Hope this clarifies it.