关于LeetCode合并两个有序链表返回正确节点的困惑
解惑LeetCode「合并两个有序链表」中的dummy节点
我正在理解LeetCode「合并两个有序链表」问题的解法,代码如下:
# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() tail = dummy while list1 and list2: if list1.val > list2.val: tail.next = list2 list2 = list2.next else: tail.next = list1 list1 = list1.next tail = tail.next if list1: tail.next = list1 elif list2: tail.next = list2 return dummy.next
我对解法逻辑无疑问,但困惑于最后一行代码。原以为dummy是val为0、next为None的ListNode对象,tail是其属性副本,后续仅修改tail.next而非dummy.next,为何dummy.next会返回合并后链表的头节点?尝试理解30分钟仍未明白,十分困惑。
核心:Python的对象引用不是属性副本
你误解了tail = dummy的含义——这行代码不是复制dummy的属性,而是让变量tail和dummy指向同一个ListNode对象。
- 初始状态:
dummy和tail都指向那个val为0、next为None的节点。此时修改其中一个变量指向对象的属性,另一个变量看到的结果完全一致。 - 进入循环后,第一次执行
tail.next = list2(或list1)时,本质是给这个共享节点的next属性赋值,所以dummy.next也会同步变成你赋值的链表节点——因为它们指向同一个对象。 - 之后的
tail = tail.next,只是让tail变量指向新的节点(刚赋值的那个list2/list1节点),但dummy变量仍然指向最初的哨兵节点,它的next已经被设置成了合并后的第一个有效节点。 - 后续所有修改
tail.next的操作,都是在给当前tail指向的节点添加后续节点,而最初的dummy节点的next始终是合并链表的头节点,最后返回它就能得到完整的合并链表。
简单说:dummy是不动的哨兵,tail是在链表上移动的指针,tail一开始和dummy指向同一个节点,第一次修改tail.next就是给dummy的next赋值,之后tail才开始往后走,dummy的next则一直保留着合并链表的起点。
内容的提问来源于stack exchange,提问作者Sebastian LeMay
相关产品推荐
相关产品推荐

