Home > Back-end >  Algorithm Question: How does linked list gets updated using Python class?
Algorithm Question: How does linked list gets updated using Python class?

Time:03-20

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

CodePudding user response:

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.

  • Related