算法问题：如何使用 Python class 更新链表？

Question

这是合并两个链表的解决方案。在代码中，我们使用place_holder来避免处理空值等情况。然而，这并不直观，因为我们在整个代码中只更新 tail，但我们在最后 return place_holder.next。

我们什么时候更新place_holder？在 while 循环中，我们只处理 list1 和 list2 节点并更新尾部。但是我们什么时候更改 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

Answer 1

下面可以直观的看到Python tutor

在 while 循环之前，place_holder 和 tail 被分配给同一个对象，即 ListNode():

place_holder = ListNode()
tail = place_holde

在 while 循环的第一次迭代中，tail.next 根据接受 if 条件的分支分配给 list1 或 list2，即

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

这也会将 place_holder.next 分配给同一个列表，因为 place_holder 和 tail 在第一次迭代中被分配给同一个对象。

在 if 条件之后，tail 被分配给不同的对象，即

tail = tail.next        # this causes place_holder and tail
                        # to no longer be assigned to the same object

因此在while循环的后续迭代中，tail在while循环中不断更新，但place_holder没有改变（因为place_holder和tail不再分配给同一个对象）

由于 place_holder.next 在函数末尾保留赋值，因此 return returns list1 或 list2。

算法问题：如何使用 Python class 更新链表？

Algorithm Question: How does linked list gets updated using Python class?

python

algorithm

class

python-3.x