I am a beginner in programming and I have a quick question on how the .next works for ListNodes. Here is my code below for one of the LeetCode problems:
class Solution
{
public ListNode mergeTwoLists(ListNode list1, ListNode list2)
{
ListNode finalHead = new ListNode(0);
ListNode tempFinalHead = finalHead;
while(list1 != null && list2 != null)
{
if(list1.val < list2.val)
{
tempFinalHead.next = list1;
list1 = list1.next; //this line
}
else
{
tempFinalHead.next = list2;
list2 = list2.next; //this line
}
tempFinalHead = tempFinalHead.next; //this line
}
if(list1 != null)
{
tempFinalHead.next = list1;
list1 = list1.next;
}
if(list2 != null)
{
tempFinalHead.next = list2;
list2 = list2.next;
}
return finalHead.next;
}
}
I commented on 3 instances where we are updating the ListNode using .next. I was wondering, how is the tempFinalHead of code for "tempFinalHead = tempFinalHead.next;" previous nodes being maintained? To elaborate here is an example:
Say this is my input: Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]
After list1.next is ran, list1 will be: 2 -> 4 from 1 -> 2 -> 4 After list2.next is ran, list2 will be 3 - > 4 from 1 -> 3 -> 4
What I am confused about is when tempFinalHead.next is ran, wouldnt the previous nodes that it was holding be gone? How is it mainting the nodes previous?
The output ended up being correct but just don't understand how tempFinalHead.next maintains all previous nodes since we are replacing it everytime with .next.
After list1.next is ran, list1 will be: 2 -> 4 from 1 -> 2 -> 4 After list2.next is ran, list2 will be 3 - > 4 from 1 -> 3 -> 4
Yes, list1 and list2 are references that walk forward and thereby reference linked lists that are shorter and shorter...
What I am confused about is when tempFinalHead.next is ran, wouldnt the previous nodes that it was holding be gone? How is it mainting the nodes previous?
Indeed, if we only could rely on tempFinalHead those nodes would be lost forever. But... we still have finalHead! That node reference has not moved, and allows us to traverse the merged list.
It may help to visualise the process for the example input you have given. When the loop starts, we have list1, list2 and a newly created node, referenced by both finalHead and tempFinalHead:
list1
↓
┌───────────┐ ┌───────────┐ ┌───────────┐
tempFinalHead │ val: 1 │ │ val: 2 │ │ val: 4 │
finalHead │ next: ────────►│ next: ────────►│ next:null │
↓ └───────────┘ └───────────┘ └───────────┘
┌───────────┐
│ val: 0 │
│ next:null │
└───────────┘
┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 3 │ │ val: 4 │
│ next: ────────►│ next: ────────►│ next:null │
└───────────┘ └───────────┘ └───────────┘
↑
list2
After the first iteration, in which the else block was executed, three of the four references moved, and one next property was updated (rewired):
list1
↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 2 │ │ val: 4 │
finalHead │ next: ────────►│ next: ────────►│ next:null │
↓ └───────────┘ └───────────┘ └───────────┘
┌───────────┐
│ val: 0 │
│ next: ────────┐
└───────────┘ │
│ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ │ val: 1 │ │ val: 3 │ │ val: 4 │
└──►│ next: ────────►│ next: ────────►│ next:null │
└───────────┘ └───────────┘ └───────────┘
↑ ↑
tempFinalHead list2
It is important to see that when list2 was assigned to the 0-node's next property, this instantly made the list that starts at finalHead longer!
We can look at the second iteration now. This time the if block executes, and we arrive in this situation:
tempFinalHead list1
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 2 │ │ val: 4 │
finalHead ┌►│ next: ────────►│ next: ────────►│ next:null │
↓ │ └───────────┘ └───────────┘ └───────────┘
┌───────────┐ │
│ val: 0 │ └──────────────┐
│ next: ────────┐ │
└───────────┘ │ │
│ ┌───────────┐│ ┌───────────┐ ┌───────────┐
│ │ val: 1 ││ │ val: 3 │ │ val: 4 │
└──►│ next: ─────┘ │ next: ────────►│ next:null │
└───────────┘ └───────────┘ └───────────┘
↑
list2
At this point we can also see that tempFinalHead references the last node that was linked into its final position. We can traverse the list from finalHead -- which never moves -- and visit some nodes (0, 1, 1) which are in their final position. The first of these does not belong to the real data, and will be discarded at the end.
The above process continues until all nodes have been wired into their correct position. Once the loop completes and also one of the two if blocks after it executes, we end with this:
tempFinalHead list1 = null
↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 2 │ │ val: 4 │
finalHead ┌►│ next: ────────►│ next: ─────┐ ┌►│ next:null │
↓ │ └───────────┘ └───────────┘│ │ └───────────┘
┌───────────┐ │ │ │
│ val: 0 │ └──────────────┐ ┌──────────────┘ └──────────────┐
│ next: ────────┐ │ │ │
└───────────┘ │ │ │ │
│ ┌───────────┐│ │ ┌───────────┐ ┌───────────┐│ list2 = null
│ │ val: 1 ││ │ │ val: 3 │ │ val: 4 ││
└──►│ next: ─────┘ └►│ next: ────────►│ next: ─────┘
└───────────┘ └───────────┘ └───────────┘
And finally finalHead moves one step forward, which results in discarding the dummy node that was created at the start (as it becomes unreachable). That reference is returned, and so the caller sees this:
┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 2 │ │ val: 4 │
┌►│ next: ────────►│ next: ─────┐ ┌►│ next:null │
│ └───────────┘ └───────────┘│ │ └───────────┘
│ │ │
└──────────────┐ ┌──────────────┘ └──────────────┐
│ │ │
│ │ │
┌───────────┐│ │ ┌───────────┐ ┌───────────┐│
│ val: 1 ││ │ │ val: 3 │ │ val: 4 ││
(returned)──►│ next: ─────┘ └►│ next: ────────►│ next: ─────┘
└───────────┘ └───────────┘ └───────────┘