leetcode_002_两数相加解析

题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

解题代码

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {dummy := &ListNode{} // 哨兵节点curr := dummy // 移动指针carry := 0 // 进位for l1 != nil || l2 != nil || carry > 0 {sum := carryif l1 != nil {sum += l1.Vall1 = l1.Next}if l2 != nil {sum += l2.Vall2 = l2.Next}carry = sum / 10curr.Next = &ListNode{Val: sum % 10}curr = curr.Next}return dummy.Next
}

解析

本题考察链表的基本操作，如创建节点、遍历链表、修改节点值以及处理链表边界情况等。

在链表操作中，边界条件（如链表为空、链表长度不等、最高位有进位等）的处理非常重要。

使用迭代方式

迭代一个链表:

// 遍历链表 l1
for l1 != nil { // 从链表头节点开始向后遍历，直到遇到空节点fmt.Println(l1.Val) // 当前节点值l1 = l1.Next // 准备遍历下一个节点
}

dummy节点总结

Dummy节点在ListNode中表示一个虚拟节点，有时候也叫着哨兵节点，通常放在链表的最前面，指向头节点。Dummy节点的使用主要是为了消除头节点的特殊性，使得代码更加优雅和易于管理。通过引入一个虚拟节点作为新链表的头部，可以避免因头节点特殊性而产生的问题。这样做的好处在于，当我们处理完链表之后，只需要返回dummy.next，由于单向链表只能从头往后遍历的性质，就可以舍弃掉dummy，返回的就是我们需要的链表。此外，在链表的操作中添加一个哑节点，让它的指针指向链表的头节点，这样在删除节点的时候，就不需要再判断删除的是否是头结点了，从而简化了操作过程。Dummy节点的使用场景主要包括作为新链表的头部，以及解决链表头部引起的极端问题。通过使用dummy节点，可以使代码更加简洁和易于理解，同时避免了一些由于头节点特殊性带来的问题。

dummy节点使用场景

1. 简化插入操作

统一操作逻辑：在没有dummy节点的情况下，插入操作需要区分是在链表头部插入还是在其他位置插入，这会导致代码逻辑变得复杂。而使用dummy节点后，所有的插入操作都可以看作是在dummy节点之后进行，从而统一了插入操作的处理逻辑。
避免空链表判断：对于空链表，传统的插入操作需要特殊处理，判断头指针是否为空。而dummy节点始终存在，它代表了链表的起始位置，不会为空，因此不需要对空链表进行额外的判断。