关于LinkedList中next参数指向及返回链表长度的疑问
关于LeetCode《两数相加》解法中返回完整链表的疑问解答
我在学习LeetCode《两数相加》问题时,看到如下解法:
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() cur = dummy carry = 0 # 注:原代码遗漏carry初始化,此处补充 while l1 or l2 or carry: v1 = l1.val if l1 else 0 v2 = l2.val if l2 else 0 # 计算当前位数值与进位 total = v1 + v2 + carry val = total % 10 carry = total // 10 cur.next = ListNode(val) # 更新指针 cur = cur.next l1 = l1.next if l1 else None l2 = l2.next if l2 else None return dummy.next
我的疑惑是:为何addTwoNumbers的返回值是从预设零节点之后的节点开始的完整链表,而非仅next指向的单个节点?
补充说明:我理解为何要使用虚拟头节点,但不明白返回值的长度。例如:
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next node1 = ListNode("A") node2 = ListNode("B") node3 = ListNode("C") node1.next = node2 node2.next = node3
当我执行print(node1.next.val)时,仅得到"B"而非包含"C"的完整序列,但在addTwoNumbers中却返回了完整的序列。
核心原因:链表节点自带后续节点的引用
你产生误解的关键在于混淆了节点的val属性和节点本身代表的整条链表链:
- 你打印
node1.next.val,只是输出了node2这个节点的数值字段,并没有遍历它后续的节点。但node2本身的next是指向node3的,node1.next这个变量本身就代表了从node2开始的完整链表。 - 如果你遍历
node1.next:
就会输出cur = node1.next while cur: print(cur.val) cur = cur.nextB和C,这就是完整的序列。
两数相加解法的链表构建逻辑
再拆解解法里的链表构建过程:
- 初始化
dummy虚拟头节点,cur指针一开始指向它。 - 每一轮循环计算当前位的数值,创建新节点,并把
cur.next指向这个新节点——此时dummy.next就会指向第一个结果节点。 - 把
cur移动到新创建的节点上,下一轮循环时,再将这个节点的next指向新的结果节点,以此类推,所有结果节点被依次串联起来。 - 最终
dummy.next指向的是第一个结果节点,而这个节点的next已经指向第二个结果节点,第二个又指向第三个……形成了完整的链表链,所以返回它就等于返回了整个结果链表。
内容的提问来源于stack exchange,提问作者bitva_na_zemlovce
相关产品推荐
相关产品推荐

