每日一題
- 21. 合并兩個有序鏈表
- 題目
- 總體思路
- 算法步驟
- 時間復雜度與空間復雜度
- 代碼
- 2. 兩數相加
- 題目
- 總體思路
- 算法步驟
- 時間復雜度與空間復雜度
- 代碼
- 知識
- 感悟
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 := 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}
}
感悟
最近老是把0和nil寫混。
寫的時候千萬要注意啊！！！
)
