Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
we have l1:
ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}
and l2:
ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}
I merge them using the following code:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
print(l1)
print(l2)
out = ListNode(-1)
temp = out
while l1 and l2:
if (l1.val < l2.val):
temp.next = l1
l1 = l1.next
else:
temp.next = l2
l2 = l2.next
temp = temp.next
print(out)
This is what out is:
ListNode{val: -1, next: ListNode{val: 1, next: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}}}}
My question is how is out getting updated?
CodePudding user response：
out gets mutated in the first iteration of the while loop.
It may help to visualise it.
Just before the loop starts, we have created a dummy node (with value -1) and referred to it with out and temp:
l1
↓
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: 1 │ │ data: 2 │ │ data: 4 │
│ next: ────────> │ next: ────────> │ next: None │
out └────────────┘ └────────────┘ └────────────┘
↓
┌────────────┐
│ data: -1 │
│ next: None │
└────────────┘
↑
temp ┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: 1 │ │ data: 3 │ │ data: 4 │
│ next: ────────> │ next: ────────> │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑
l2
In the first iteration we get into the else block, where temp is mutated. Since temp and out reference the same object, this mutates out.
l1
↓
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: 1 │ │ data: 2 │ │ data: 4 │
│ next: ────────> │ next: ────────> │ next: None │
out └────────────┘ └────────────┘ └────────────┘
↓
┌────────────┐
│ data: -1 │
│ next: ──────┐
└────────────┘│
↑ │
temp │ ┌────────────┐ ┌────────────┐ ┌────────────┐
│ │ data: 1 │ │ data: 3 │ │ data: 4 │
└> │ next: ────────> │ next: ────────> │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑
l2
After this update, both l2 and temp are "moved" to refer to their successor. This ends the first iteration:
l1
↓
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: 1 │ │ data: 2 │ │ data: 4 │
│ next: ────────> │ next: ────────> │ next: None │
out └────────────┘ └────────────┘ └────────────┘
↓
┌────────────┐
│ data: -1 │
│ next: ──────┐
└────────────┘│
│
│ ┌────────────┐ ┌────────────┐ ┌────────────┐
│ │ data: 1 │ │ data: 3 │ │ data: 4 │
└> │ next: ────────> │ next: ────────> │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑ ↑
temp l2
We don't really have to continue through the algorithm, as from now on out will not be mutated again: that job has been done. But let's just continue with one more iteration (the second iteration). There we get into the if block, and temp gets mutated again (but this time, it is not a synonym for out):
l1
↓
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: 1 │ │ data: 2 │ │ data: 4 │
┌> │ next: ────────> │ next: ────────> │ next: None │
out │ └────────────┘ └────────────┘ └────────────┘
↓ └────────────────┐
┌────────────┐ │
│ data: -1 │ │
│ next: ──────┐ │
└────────────┘│ │
│ │
│ ┌────────────┐│ ┌────────────┐ ┌────────────┐
│ │ data: 1 ││ │ data: 3 │ │ data: 4 │
└> │ next: ──────┘ │ next: ────────> │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑ ↑
temp l2
...and both l1 and temp move to their successors:
temp l1
↓ ↓
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: 1 │ │ data: 2 │ │ data: 4 │
┌> │ next: ────────> │ next: ────────> │ next: None │
out │ └────────────┘ └────────────┘ └────────────┘
↓ └────────────────┐
┌────────────┐ │
│ data: -1 │ │
│ next: ──────┐ │
└────────────┘│ │
│ │
│ ┌────────────┐│ ┌────────────┐ ┌────────────┐
│ │ data: 1 ││ │ data: 3 │ │ data: 4 │
└> │ next: ──────┘ │ next: ────────> │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑
l2
Continuing like that, temp will remain the tail of the resulting list that is being wired. After the last iteration, we will have this:
l1
↓
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: 1 │ │ data: 2 │ │ data: 4 │
┌> │ next: ────────> │ next: ──────┐ │ next: None │
out │ └────────────┘ └────────────┘│ └────────────┘
↓ └────────────────┐ ┌───────────────┘
┌────────────┐ │ │
│ data: -1 │ │ │
│ next: ──────┐ │ │
└────────────┘│ │ │
│ │ │
│ ┌────────────┐│ │ ┌────────────┐ ┌────────────┐
│ │ data: 1 ││ │ │ data: 3 │ │ data: 4 │
└> │ next: ──────┘ └>│ next: ────────> │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑
temp
The job is not entirely done, as some code is missing from the snippet you have posted. When the while loop exits, one of l1 or l2 will not be None, and that represents a part that still needs to be appended to the resulting list. As temp refers to the current tail of the resulting list, we should set its next reference to either l1 or l2 -- whichever is not None.
So the code should have something like the following statement after the loop:
temp.next = l1 or l2
...which results in:
l1
↓
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: 1 │ │ data: 2 │ │ data: 4 │
┌> │ next: ────────> │ next: ──────┐ ┌>│ next: None │
out │ └────────────┘ └────────────┘│ │ └────────────┘
↓ └────────────────┐ ┌───────────────┘ └───────────────┐
┌────────────┐ │ │ │
│ data: -1 │ │ │ │
│ next: ──────┐ │ │ │
└────────────┘│ │ │ │
│ │ │ │
│ ┌────────────┐│ │ ┌────────────┐ ┌────────────┐│
│ │ data: 1 ││ │ │ data: 3 │ │ data: 4 ││
└> │ next: ──────┘ └>│ next: ────────> │ next: ──────┘
└────────────┘ └────────────┘ └────────────┘
↑
temp
And finally, the function should return the result. As out refers to a dummy node, we should not just return out, but out.next:
return out.next
The returned list reference will be to this:
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: 1 │ │ data: 2 │ │ data: 4 │
┌> │ next: ────────> │ next: ──────┐ ┌>│ next: None │
│ └────────────┘ └────────────┘│ │ └────────────┘
└────────────────┐ ┌───────────────┘ └───────────────┐
│ │ │
┌────────────┐│ │ ┌────────────┐ ┌────────────┐│
│ data: 1 ││ │ │ data: 3 │ │ data: 4 ││
returned → │ next: ──────┘ └>│ next: ────────> │ next: ──────┘
└────────────┘ └────────────┘ └────────────┘
I hope this clarifies it.
CodePudding user response：
If it helps, you don't even need any temporary nodes. You can relink the existing nodes which makes it much simpler:
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not (l1 and l2):
return l1 or l2
if l2.val < l1.val:
l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1