文章目录
- 21.合并两个有序链表
- 题目：
- 思路：迭代
- 代码实现（Go）：
- 2.两数相加
- 题目：
- 思路：
- 代码实现（Go）：
21.合并两个有序链表
题目：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
思路：迭代
-
创建一个虚拟头节点（dummy）
- 方便操作链表，最终返回
dummy.Next。
- 方便操作链表，最终返回
-
定义一个指针
current指向 dummy- 用来构建新的链表。
-
遍历两个链表 l1 和 l2
-
比较 l1 和 l2 当前节点的值：
- 如果 l1 的值小，就将 l1 的节点接到
current.Next，然后 l1 向后移动。 - 如果 l2 的值小，就将 l2 的节点接到
current.Next，然后 l2 向后移动。
- 如果 l1 的值小，就将 l1 的节点接到
-
current每次都向后移动。
-
-
处理剩余节点
- 当其中一个链表遍历完后，另一个链表可能还有剩余节点，直接接到
current.Next。
- 当其中一个链表遍历完后，另一个链表可能还有剩余节点，直接接到
-
返回结果
- 返回
dummy.Next，跳过虚拟头节点。
- 返回
时间复杂度：O(n + m)
空间复杂度：O(1)（除了返回的新链表节点，没有额外空间开销）
代码实现（Go）：
详细注解：
// package main// import "fmt"// type ListNode struct {
// Val int
// Next *ListNode
// }func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {// 创建一个虚拟头节点dummy := &ListNode{} // 已分配了一个空节点，可直接使用cur := dummy// 遍历两个链表，比较节点值for l1 != nil && l2 != nil {if l1.Val < l2.Val {cur.Next = l1l1 = l1.Next} else {cur.Next = l2l2 = l2.Next}cur = cur.Next}// 将剩余节点接上if l1 != nil {cur.Next = l1} else {cur.Next = l2}// 返回合并后的链表（跳过虚拟头节点）return dummy.Next
}// func main() {
// // 创建链表 l1: 1->2->4
// l1 := &ListNode{
// Val: 1,
// Next: &ListNode{
// Val: 2,
// Next: &ListNode{
// Val: 4,
// Next: nil,
// },
// },
// }// // 创建链表 l2: 1->3->4
// l2 := &ListNode{
// Val: 1,
// Next: &ListNode{
// Val: 3,
// Next: &ListNode{
// Val: 4,
// Next: nil,
// },
// },
// }// merged := mergeTwoLists(l1, l2)// // 输出 1->1->2->3->4->4
// for merged != nil {
// fmt.Print(merged.Val)
// if merged.Next != nil {
// fmt.Print("->")
// }
// merged = merged.Next
// }
// }无注释：
package mainimport "fmt"type ListNode struct {Val intNext *ListNode
}func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {dummy := &ListNode{}cur := dummyfor l1 != nil && l2 != nil {if l1.Val < l2.Val {cur.Next = l1l1 = l1.Next} else {cur.Next = l2l2 = l2.Next}cur = cur.Next}if l1 != nil {cur.Next = l1} else {cur.Next = l2}return dummy.Next
}func main() {l1 := &ListNode{Val: 1,Next: &ListNode{Val: 2,Next: &ListNode{Val: 4,Next: nil,},},}l2 := &ListNode{Val: 1,Next: &ListNode{Val: 3,Next: &ListNode{Val: 4,Next: nil,},},}merged := mergeTwoLists(l1, l2)for merged != nil {fmt.Print(merged.Val)if merged.Next != nil {fmt.Print("->")}merged = merged.Next}
}2.两数相加
题目：
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：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]
提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
思路：
-
逐位相加
- 因为链表存储的数字是逆序的，所以直接从头节点开始相加就行。
- 每次相加
l1.Val + l2.Val + carry，得到sum。
-
计算进位
- 当前节点的值是
sum % 10。 - 进位值是
sum / 10（Go 里用整除）。
- 当前节点的值是
-
指针后移
l1、l2向后移动，如果某个链表已经走到nil，就按 0 处理。
-
处理最后的进位
- 如果两个链表都结束了，但还有
carry > 0，要新建一个节点存储进位。
- 如果两个链表都结束了，但还有
-
返回结果
- 同样用一个虚拟头节点（dummy）简化逻辑，最后返回
dummy.Next。
- 同样用一个虚拟头节点（dummy）简化逻辑，最后返回
在第一次循环时，我们无法往一个空节点的末尾添加节点。这里的技巧是，创建一个虚拟头节点（dummy node），当成初始的「空链表」。
循环结束后，虚拟头节点的下一个节点就是最终要返回的链表头节点。相当于占位头。
- 时间复杂度：O(max(n, m)) 遍历两个链表的长度。
- 空间复杂度：O(1) 只用常量级变量（不计结果链表本身）。
代码实现（Go）：
详细注解：
// package main// import "fmt"// type ListNode struct {
// Val int
// Next *ListNode
// }func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {dummy := &ListNode{} // 虚拟头节点cur := dummycarry := 0 // 进位for l1 != nil || l2 != nil || carry != 0 { // 有一个不是空节点，或者还有进位，就继续迭代if l1 != nil {carry += l1.Val // 节点值和进位加在一起l1 = l1.Next // 下一个节点}if l2 != nil {carry += l2.Val // 节点值和进位加在一起l2 = l2.Next // 下一个节点}cur.Next = &ListNode{Val: carry % 10} // 当前位carry /= 10 // 新的进位cur = cur.Next // 下一个节点}return dummy.Next
}
// 当 l1 或 l2 为 nil 时，就不会执行 carry += l1.Val 或 carry += l2.Val
// 也就是说，相当于对空链表这一位加 0，不会影响总和// func main() {
// // l1 = [2,4,3]
// l1 := &ListNode{
// Val: 2,
// Next: &ListNode{
// Val: 4,
// Next: &ListNode{
// Val: 3,
// Next: nil,
// },
// },
// }// // l2 = [5,6,4]
// l2 := &ListNode{
// Val: 5,
// Next: &ListNode{
// Val: 6,
// Next: &ListNode{
// Val: 4,
// Next: nil,
// },
// },
// }// res := addTwoNumbers(l1, l2)// // 输出: 7->0->8
// for res != nil {
// fmt.Print(res.Val)
// if res.Next != nil {
// fmt.Print("->")
// }
// res = res.Next
// }
// }无注释：
package mainimport "fmt"type ListNode struct {Val intNext *ListNode
}func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {dummy := &ListNode{}cur := dummycarry := 0for l1 != nil || l2 != nil || carry != 0 {if l1 != nil {carry += l1.Vall1 = l1.Next}if l2 != nil {carry += l2.Vall2 = l2.Next}cur.Next = &ListNode{Val: carry % 10}carry /= 10cur = cur.Next}return dummy.Next
}func main() {l1 := &ListNode{Val: 2,Next: &ListNode{Val: 4,Next: &ListNode{Val: 3,Next: nil,},},}l2 := &ListNode{Val: 5,Next: &ListNode{Val: 6,Next: &ListNode{Val: 4,Next: nil,},},}res := addTwoNumbers(l1, l2)for res != nil {fmt.Print(res.Val)if res.Next != nil {fmt.Print("->")}res = res.Next}
}
