每日一题
2025.8.30
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 node）作为新链表的起始点，然后逐个比较两个链表的节点值，选择较小的节点连接到新链表中，最后将剩余的节点直接连接到最后。
算法步骤
- 初始化：创建哑节点和尾指针
- 比较合并：同时遍历两个链表，选择较小值的节点连接
- 处理剩余：将未遍历完的链表直接连接到尾部
- 返回结果：返回哑节点的下一个节点
时间复杂度与空间复杂度
- 时间复杂度：O(n + m)
- 需要遍历两个链表的所有节点
- n 和 m 分别是两个链表的长度
- 最坏情况下需要比较 n + m 次
- 空间复杂度：O(1)
- 只使用了常数级别的额外空间（哑节点和几个指针）
- 原地操作，不创建新节点，直接重用原有节点
代码
golang
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
dump := &ListNode{}
tail := dump
for list1 != nil && list2 != nil {
if list1.Val >= list2.Val {
tail.Next = list2
list2 = list2.Next
}else {
tail.Next = list1
list1 = list1.Next
}
tail = tail.Next
}
if list1 != nil {
tail.Next = list1
}else {
tail.Next = list2
}
return dump.Next
}
/**
* 合并两个有序链表
* 将两个升序链表合并为一个新的升序链表并返回
*
* @param list1 *ListNode 第一个有序链表的头节点
* @param list2 *ListNode 第二个有序链表的头节点
* @return *ListNode 合并后的新链表的头节点
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
// 创建哑节点（dummy node）作为新链表的起始前驱节点
// 使用哑节点可以简化代码，避免处理头节点的特殊情况
dummy := &ListNode{}
// 尾指针，指向新链表的最后一个节点
// 初始时指向哑节点，随着节点的添加而移动
tail := dummy
// 同时遍历两个链表，直到其中一个链表遍历完毕
// 比较两个链表当前节点的值，选择较小的节点添加到新链表
for list1 != nil && list2 != nil {
if list1.Val <= list2.Val {
// 如果list1的当前节点值小于等于list2的当前节点值
// 将list1的当前节点连接到新链表的尾部
tail.Next = list1
// list1指针前进到下一个节点
list1 = list1.Next
} else {
// 如果list2的当前节点值小于list1的当前节点值
// 将list2的当前节点连接到新链表的尾部
tail.Next = list2
// list2指针前进到下一个节点
list2 = list2.Next
}
// 尾指针前进到新添加的节点，保持指向新链表的最后一个节点
tail = tail.Next
}
// 处理剩余的节点：将未遍历完的链表直接连接到新链表的尾部
// 由于两个链表都是有序的，剩余部分本身已经是有序的
if list1 != nil {
// 如果list1还有剩余节点，直接全部连接
tail.Next = list1
} else {
// 如果list2还有剩余节点，或者两个链表都为空，连接list2
// 如果两个链表都为空，list2为nil，连接nil也是正确的
tail.Next = list2
}
// 返回哑节点的下一个节点，即新链表的实际头节点
// 哑节点本身不存储有效数据，只是辅助节点
return dummy.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
题目数据保证列表表示的数字不含前导零
总体思路
这个算法模拟了手工竖式加法的过程，将两个用链表逆序存储的数字相加。数字的低位存储在链表的前面，高位存储在后面，这样可以直接从头开始逐位相加，正确处理进位问题。
算法步骤
- 初始化：创建哑节点、尾指针和进位变量
- 逐位相加：同时遍历两个链表，对应位相加加上进位
- 处理进位：计算当前位的值和新的进位
- 处理剩余：处理链表长度不一致和最终进位的情况
- 返回结果：返回结果链表的头节点
时间复杂度与空间复杂度
- 时间复杂度：O(max(n, m))
- 需要遍历较长的链表
- n 和 m 分别是两个链表的长度
- 每个节点处理时间是常数时间
- 空间复杂度：O(max(n, m))
- 需要创建新的链表存储结果
- 最坏情况下结果链表长度为 max(n, m) + 1（有进位时）
- 只存储结果，不存储中间过程
代码
golang
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dump := &ListNode{}
tail := dump
carry := 0
for l1 != nil || l2 != nil || carry != 0 {
val1, val2 := 0, 0
if l1 != nil {
val1 = l1.Val
l1 = l1.Next
}
if l2 != nil {
val2 = l2.Val
l2 = l2.Next
}
sum := val1 + val2 + carry
val := sum % 10
carry = sum / 10
tail.Next = &ListNode{Val: val}
tail = tail.Next
}
return dump.Next
}
/**
* 两个逆序链表表示的数字相加
* 数字的低位存储在链表前面，高位存储在后面
* 例如：数字 342 表示为 2 -> 4 -> 3
*
* @param l1 *ListNode 第一个数字的链表表示（逆序）
* @param l2 *ListNode 第二个数字的链表表示（逆序）
* @return *ListNode 相加结果的链表表示（逆序）
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
// 创建哑节点（dummy node）作为结果链表的起始前驱节点
// 使用哑节点可以简化代码，避免处理头节点的特殊情况
dummy := &ListNode{}
// 尾指针，指向结果链表的最后一个节点
// 用于高效地在链表尾部添加新节点
tail := dummy
// 进位值，表示上一位相加产生的进位
// 初始为0，因为第一位相加没有前一位的进位
carry := 0
// 循环条件：只要任一链表还有节点，或者还有进位需要处理，就继续循环
// l1 != nil: 第一个链表还有数字位
// l2 != nil: 第二个链表还有数字位
// carry != 0: 还有进位需要处理（重要！处理最后一位的进位）
for l1 != nil || l2 != nil || carry != 0 {
// 初始化当前位的值，如果对应链表为空则值为0
val1, val2 := 0, 0
// 处理第一个链表的当前位
if l1 != nil {
val1 = l1.Val // 获取当前位的值
l1 = l1.Next // 指针移动到下一位
}
// 处理第二个链表的当前位
if l2 != nil {
val2 = l2.Val // 获取当前位的值
l2 = l2.Next // 指针移动到下一位
}
// 计算当前位的总和：两个数字位加上进位
sum := val1 + val2 + carry
// 计算当前位的值：取总和除以10的余数
// 例如：7 % 10 = 7, 12 % 10 = 2
newVal := sum % 10
// 计算新的进位值：取总和除以10的商
// 例如：7 / 10 = 0, 12 / 10 = 1
carry = sum / 10
// 创建新节点存储当前位的值，并连接到结果链表尾部
tail.Next = &ListNode{Val: newVal}
// 移动尾指针到新添加的节点，保持指向链表尾部
tail = tail.Next
}
// 返回哑节点的下一个节点，即结果链表的实际头节点
// 哑节点本身不存储有效数据，只是辅助节点
return dummy.Next
}
知识
各种结构体初始化方式
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func main() {
// 方式1：字段名初始化（最常用）
node1 := &ListNode{
Val: 1,
Next: nil,
}
fmt.Printf("节点1: Val=%d, Next=%v\n", node1.Val, node1.Next)
// 方式2：顺序初始化
node2 := &ListNode{2, nil}
fmt.Printf("节点2: Val=%d, Next=%v\n", node2.Val, node2.Next)
// 方式3：创建结构体后取地址
node3 := ListNode{Val: 3}
node3Ptr := &node3
fmt.Printf("节点3: Val=%d, Next=%v\n", node3Ptr.Val, node3Ptr.Next)
// 方式4：使用new函数
node4 := new(ListNode)
node4.Val = 4
fmt.Printf("节点4: Val=%d, Next=%v\n", node4.Val, node4.Next)
// 在链表操作中的实际使用
dummy := &ListNode{}
tail := dummy
// 这就是你在代码中看到的语法
tail.Next = &ListNode{Val: 5} // 创建新节点并连接
tail = tail.Next
tail.Next = &ListNode{Val: 6} // 继续添加节点
tail = tail.Next
fmt.Print("链表: ")
current := dummy.Next
for current != nil {
fmt.Printf("%d", current.Val)
if current.Next != nil {
fmt.Print(" -> ")
}
current = current.Next
}
}
感悟
最近老是把0和nil写混。
写的时候千万要注意啊！！！