Here is a solution to merging two linked lists. In the code, we use place_holder to avoid cases such as dealing with null values. However, this is not intuitive as we only update tail throughout the code but we return place_holder.next at the end.
When are we updating place_holder? within the while loop we’re only working with list1 and list2 nodes and updating the tail. But when are we changing the values of place_holder?
class ListNode:
def __init__(self, val: int = 0, *vals: int) -> None:
self.val = val
self.next = ListNode(*vals) if vals else None
def __str__(self) -> str:
s = f"{str(self.val)}"
if self.next:
s += f" -> {self.next}"
return s
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
place_holder = ListNode()
tail = place_holder
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1 is None:
tail.next = list2
if list2 is None:
tail.next = list1
return place_holder.next
>Solution :
The following can be seen visually in Python tutor
Before the while loop, place_holder and tail are assigned to the same object i.e. ListNode():
place_holder = ListNode()
tail = place_holde
In the first iteration of the while loop, tail.next is assigned to either list1 or list2 based upon which branch taking in the if condtion i.e.
if list1.val < list2.val
tail.next = list1 # tail assigned to list1
list1 = list1.next
else:
tail.next = list2 # tail assigned to list2
list2 = list2.next
This also assigns place_holder.next to the same list since place_holder and tail are assigned to the same object in the first iteration.
After the if condition, tail is assigned to a different object i.e.
tail = tail.next # this causes place_holder and tail
# to no longer be assigned to the same object
So in subsequent iterations of the while loop, tail keeps being updated in the while loop but place_holder is not changed (since place_holder and tail are no longer assigned to the same object)
Since place_holder.next keeps it assignment at the end of the function the return either returns list1 or list2.