LeetCode 21:合并两个有序链表解法理解困惑
合并两个有序链表解法疑问
问题背景
题目为合并两个有序链表,单链表定义如下:
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next
我无法独立想出解法,也不理解ListNode的工作原理,因此找到了他人的解法,希望搞懂它的运行机制。原解法代码如下:
class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: cur = dummy = ListNode() while list1 and list2: if list1.val < list2.val: cur.next = list1 list1, cur = list1.next, list1 else: cur.next = list2 list2, cur = list2.next, list2 if list1 or list2: cur.next = list1 if list1 else list2 return dummy.next
为了理解运行逻辑,我给代码添加了打印dummy和cur的语句:
class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: cur = dummy = ListNode() print ("1. dummy = " + str(dummy)) print ("1. cur = " + str(cur)) while list1 and list2: if list1.val < list2.val: cur.next = list1 list1, cur = list1.next, list1 else: cur.next = list2 list2, cur = list2.next, list2 print ("2. dummy = " + str(dummy)) print ("2. cur = " + str(cur)) if list1 or list2: cur.next = list1 if list1 else list2 print ("3. dummy = " + str(dummy)) print ("3. cur = " + str(cur)) print("answer = " + str(dummy)) # return dummy.next
控制台部分输出如下:
1. dummy = ListNode{val: 0, next: None} 1. cur = ListNode{val: 0, next: None} # 循环开始前:cur 和 dummy 指向同一个空的ListNode 2. dummy = ListNode{val: 0, next: ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}} 2. cur = ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}} # 第一次循环后,疑问产生
我的疑问
循环开始前dummy和cur指向同一个空节点,进入else分支后,我原本以为cur和dummy应该同步变化,但打印结果显示dummy仍为初始节点,cur却指向了list2的第一个节点,这是为什么?
内容的提问来源于stack exchange,提问作者childoflogos
相关产品推荐
相关产品推荐

