算法问题:如何使用Python类更新链表

Question

这里有一个合并两个链表的解决方案。在代码中，我们使用place_holder来避免诸如处理null值之类的情况。然而，这并不直观，因为我们在整个代码中只更新tail，但在最后返回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教程中直观地看到

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

place_holder = ListNode()
tail = place_holde

在while循环的第一次迭代中，tail.next被分配给list1或list2，这取决于哪个分支接受if条件，即

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.next        # this causes place_holder and tail
# to no longer be assigned to the same object

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

由于place_holder.next在函数末尾保留赋值，因此返回值要么返回list1，要么返回list2。