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 := dumpfor list1 != nil && list2 != nil {if list1.Val >= list2.Val {tail.Next = list2list2 = list2.Next}else {tail.Next = list1list1 = 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 := dumpcarry := 0for l1 != nil || l2 != nil || carry != 0 {val1, val2 := 0, 0if l1 != nil {val1 = l1.Vall1 = l1.Next}if l2 != nil {val2 = l2.Vall2 = l2.Next}sum := val1 + val2 + carryval := sum % 10carry = sum / 10tail.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 {// 初始化当前位的值，如果对应链表为空则值为0val1, 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 = 2newVal := sum % 10// 计算新的进位值：取总和除以10的商// 例如：7 / 10 = 0, 12 / 10 = 1carry = sum / 10// 创建新节点存储当前位的值，并连接到结果链表尾部tail.Next = &ListNode{Val: newVal}// 移动尾指针到新添加的节点，保持指向链表尾部tail = tail.Next}// 返回哑节点的下一个节点，即结果链表的实际头节点// 哑节点本身不存储有效数据，只是辅助节点return dummy.Next
}

知识

各种结构体初始化方式

package mainimport "fmt"type ListNode struct {Val  intNext *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 := &node3fmt.Printf("节点3: Val=%d, Next=%v\n", node3Ptr.Val, node3Ptr.Next)// 方式4：使用new函数node4 := new(ListNode)node4.Val = 4fmt.Printf("节点4: Val=%d, Next=%v\n", node4.Val, node4.Next)// 在链表操作中的实际使用dummy := &ListNode{}tail := dummy// 这就是你在代码中看到的语法tail.Next = &ListNode{Val: 5}  // 创建新节点并连接tail = tail.Nexttail.Next = &ListNode{Val: 6}  // 继续添加节点tail = tail.Nextfmt.Print("链表: ")current := dummy.Nextfor current != nil {fmt.Printf("%d", current.Val)if current.Next != nil {fmt.Print(" -> ")}current = current.Next}
}