Problem: 21. 合并兩個有序鏈表
題目:將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。
文章目錄
- 整體思路
- 完整代碼
- 時空復雜度
- 時間復雜度:O(M + N)
- 空間復雜度:O(1)
整體思路
這段代碼旨在解決一個基礎且經典的鏈表問題:合并兩個有序鏈表 (Merge Two Sorted Lists)。問題要求將兩個已按升序排列的鏈表合并為一個新的、仍然保持升序的鏈表。
該算法采用了一種非常標準和高效的 “迭代法”,通過一個 “虛擬頭節點(Dummy Node)” 技巧來簡化代碼邏輯。
-
虛擬頭節點(Dummy Node)的作用:
- 算法首先創建了一個名為
dummy
的新節點。這個節點本身不存儲任何有效數據,它的主要作用是作為新合并鏈表的哨兵或占位符。 - 優勢:使用
dummy
節點可以避免處理“新鏈表為空”的邊界情況。我們始終可以安全地向dummy.next
添加第一個有效節點,而無需編寫if (newList == null)
這樣的判斷。最后,我們只需返回dummy.next
即可得到真正的新鏈表頭。 - 一個
tail
指針被初始化為dummy
,它將始終指向新合并鏈表的尾部,用于方便地追加新節點。
- 算法首先創建了一個名為
-
迭代合并:
- 算法使用一個
while
循環,只要兩個輸入鏈表list1
和list2
都不為空,就持續進行比較和合并。 - 在循環的每一步,比較
list1.val
和list2.val
的大小:- 如果
list1.val < list2.val
:說明list1
的當前節點值更小,應該被先加入到新鏈表中。于是,將tail.next
指向list1
,然后將list1
指針向前移動一步 (list1 = list1.next
)。 - 否則 (
list1.val >= list2.val
):說明list2
的當前節點值更小或相等,它應該被加入新鏈表。將tail.next
指向list2
,然后移動list2
指針。
- 如果
- 在將一個節點鏈接到新鏈表后,必須將
tail
指針也向前移動 (tail = tail.next
),使其始終指向新鏈表的最后一個節點,為下一次追加做準備。
- 算法使用一個
-
處理剩余部分:
- 當
while
循環結束時,意味著list1
或list2
(或兩者都)已經為空。 - 此時,最多只有一個鏈表還有剩余的節點。由于輸入鏈表本身就是有序的,這個剩余的部分也必然是有序的,并且其所有節點的值都大于或等于已合并鏈表中的所有值。
- 因此,我們無需再逐個比較,直接將
tail.next
指向那個非空的剩余鏈表即可。 - 代碼
tail.next = list1 != null ? list1 : list2;
巧妙地實現了這一邏輯。
- 當
-
返回結果:
- 最后,返回
dummy.next
,它指向新合并鏈表的真正頭節點。
- 最后,返回
完整代碼
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {/*** 將兩個升序鏈表合并為一個新的升序鏈表。* @param list1 第一個有序鏈表的頭節點* @param list2 第二個有序鏈表的頭節點* @return 合并后新鏈表的頭節點*/public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 創建一個虛擬頭節點(dummy node),作為新鏈表的哨兵。ListNode dummy = new ListNode();// tail 指針用于追蹤新鏈表的尾部,方便追加節點。ListNode tail = dummy;// 步驟 1: 迭代比較和合并,直到其中一個鏈表為空。while (list1 != null && list2 != null) {// 比較兩個鏈表當前節點的值if (list1.val < list2.val) {// 如果 list1 的值更小,將 list1 的當前節點鏈接到新鏈表尾部tail.next = list1;// 移動 list1 的指針到下一個節點list1 = list1.next;} else {// 否則,將 list2 的當前節點鏈接到新鏈表尾部tail.next = list2;// 移動 list2 的指針到下一個節點list2 = list2.next;}// 無論哪個節點被鏈接,都要將 tail 指針移動到新鏈表的當前末尾tail = tail.next;}// 步驟 2: 處理剩余的鏈表部分。// 循環結束后,最多只有一個鏈表還有剩余節點。// 直接將新鏈表的尾部鏈接到這個剩余鏈表的頭部。tail.next = (list1 != null) ? list1 : list2;// 步驟 3: 返回虛擬頭節點的下一個節點,即新鏈表的真正頭節點。return dummy.next;}
}
時空復雜度
時間復雜度:O(M + N)
- 循環分析:
- 算法的核心是
while
循環。在每次迭代中,list1
或list2
中的一個指針會向前移動一步。 - 這個循環會一直持續到其中一個鏈表被完全遍歷完。
- 設
list1
的長度為M
,list2
的長度為N
。while
循環的總迭代次數等于M
和N
中較小者的長度。 - 處理剩余部分的操作是 O(1)。
- 總的來說,算法需要遍歷兩個鏈表的所有節點恰好一次。
- 算法的核心是
綜合分析:
算法的時間復雜度與兩個鏈表的總長度成線性關系,即 O(M + N)。
空間復雜度:O(1)
- 主要存儲開銷:該算法是在原地重新鏈接(re-wire)輸入鏈表的節點,并沒有為新鏈表創建新的節點。
- 輔助變量:只創建了
dummy
和tail
兩個額外的指針變量。這些變量的數量是固定的,與鏈表長度無關。
綜合分析:
算法所需的額外輔助空間是常數級別的。因此,其空間復雜度為 O(1)。這是一個空間效率最優的迭代解法。
【LeetCode 熱題 100】21. 合并兩個有序鏈表——(解法二)遞歸法
參考靈神