前言 😊

在 Android 開發中，算法與數據結構是基本功之一，而鏈表（Linked List）作為常見的數據結構，經常出現在各類面試題與實際業務場景中。本文將以 Android Kotlin 為語言，結合 LeetCode 上的經典鏈表題目，詳細講解鏈表的基本概念、常見操作以及經常考到的算法題目（如：反轉鏈表、合并有序鏈表、判斷鏈表是否有環等），并提供 Kotlin 實現代碼、時間復雜度與空間復雜度分析，最后附帶最佳實踐建議與面試拓展。

• 適用場景：想要系統學習鏈表算法、準備 Android/Kotlin 面試、提升算法能力的讀者。
• 閱讀收益：掌握鏈表基本操作技巧、理解常見題型的解題思路與 Kotlin 代碼實現、積累面試常見變形題思路與調試經驗。

---

目錄 📑

1. 鏈表基礎知識回顧與 Kotlin 實現
2. 反轉鏈表（Reverse Linked List）詳解
3. 合并兩個有序鏈表（Merge Two Sorted Lists）
4. 判斷鏈表是否有環（Linked List Cycle）
5. 其他常見鏈表題目匯總與進階分析
6. 總結與最佳實踐建議

---

1. 鏈表基礎知識回顧與 Kotlin 實現 🧐

1.1 鏈表的基本概念

鏈表（Linked List）是一種 線性數據結構，由一系列節點（Node）組成，每個節點包含數據域和指向下一個節點的指針（或引用）。與數組相比，鏈表的優勢在于 插入和刪除操作 的時間復雜度可以做到 O(1)（定位到節點之后），但是隨機訪問的時間復雜度為 O(n)（需要遍歷）。

常見鏈表類型包括：

1. 單向鏈表（Singly Linked List）：每個節點只保存指向下一個節點的引用。
2. 雙向鏈表（Doubly Linked List）：每個節點同時保存指向前一個節點和下一個節點的引用，支持雙向遍歷。
3. 循環鏈表（Circular Linked List）：在單向或雙向鏈表的基礎上，將尾節點的 next 指向頭節點，形成環。

鏈表的優缺點

• 優點：

  • 插入、刪除操作不需整體移動元素，只需修改指針，效率較高。
  • 空間利用上，鏈表不需要一次性分配連續空間，可動態增長。

• 缺點：

  • 隨機訪問效率低，訪問元素需要從頭節點依次遍歷。
  • 額外空間：由于需要存儲指針/引用，相對于數組有額外開銷。
  • 在某些場景下，頻繁的對象創建與垃圾回收會帶來性能損耗。

1.2 Kotlin 中鏈表節點的定義

在 Kotlin 中，我們可以通過一個簡單的 data class 來表示單鏈表的節點：

/*** 單鏈表節點定義* @param value 節點保存的值* @param next 指向下一個節點（可空）*/
data class ListNode(var value: Int, var next: ListNode? = null)

• value：節點保存的整型數據，可以根據需求修改為任意數據類型。
• next：指向下一個節點，使用可空類型 ListNode?，當 next == null 時表示當前節點是尾節點。

💡 Kotlin 小技巧：

• data class 自動生成 toString()、equals()、hashCode() 等方法，方便調試和打印。
• 可以結合可空類型與安全調用 ?. 有效避免空指針異常。

1.3 鏈表常見基礎操作

1. 遍歷鏈表

   • 時間復雜度：O(n)，空間復雜度：O(1)。

   • 代碼示例：

     fun traverse(head: ListNode?) {var current = headwhile (current != null) {println(current.value)current = current.next}
     }
     

2. 插入節點

   • 可以在頭部插入、尾部插入或指定位置插入。

   • 以頭插法為例：

     fun insertAtHead(head: ListNode?, newValue: Int): ListNode {val newNode = ListNode(newValue)newNode.next = headreturn newNode // 返回新的頭節點
     }
     

3. 刪除節點

   • 需要找到待刪除節點的前一個節點，修改其 next 指向下一個節點即可。

   • 以刪除值為 target 的第一個節點為例：

     fun deleteNode(head: ListNode?, target: Int): ListNode? {// 虛擬頭節點，簡化刪除頭節點的邏輯val dummy = ListNode(-1).apply { next = head }var prev: ListNode? = dummyvar curr = headwhile (curr != null) {if (curr.value == target) {prev?.next = curr.nextbreak}prev = currcurr = curr.next}return dummy.next
     }
     

4. 獲取鏈表長度

   fun getLength(head: ListNode?): Int {var length = 0var curr = headwhile (curr != null) {length++curr = curr.next}return length
   }
   

🔍 復雜度小結：

• 遍歷、獲取長度：O(n) 時間，O(1) 空間
• 插入、刪除（定位到節點后）：O(1) 時間（不含尋找節點的時間），O(1) 空間

---

2. 反轉鏈表（Reverse Linked List）詳解 🔄

2.1 題目描述與分析（LeetCode 206） 📌

• 題目原文（簡體翻譯）：
  給你單鏈表的頭節點 head，請你反轉鏈表，并返回反轉后的鏈表。

• 示例：

  輸入：1 -> 2 -> 3 -> 4 -> 5 -> null
  輸出：5 -> 4 -> 3 -> 2 -> 1 -> null
  

• 思路要點：

  1. 迭代法（Iterative）：利用「前驅節點」prev、「當前節點」curr、「下一個節點」nextTemp 三個指針依次反轉指向。
  2. 遞歸法（Recursive）：先遞歸到鏈表尾部，再在遞歸回溯的過程中反轉指向。

💡 注意：鏈表反轉操作會修改原鏈表的指針指向，請謹慎處理 null 邊界和頭尾節點的更新。

---

2.2 迭代法詳解 ?

2.2.1 解題思路

1. 初始化兩個指針：

   • prev = null（表示反轉后鏈表的尾部）
   • curr = head（表示當前待處理的節點）

2. 進入循環，當 curr != null 時：

   • 先保存 curr.next 到臨時變量 nextTemp，以免修改指向后丟失下一個節點。
   • 將 curr.next 指向 prev，完成當前節點的反轉。
   • 然后讓 prev 指向 curr，curr 指向 nextTemp，繼續處理下一個節點。

3. 循環結束后，prev 剛好指向反轉后鏈表的頭節點，返回 prev 即可。

2.2.2 Kotlin 實現代碼

/*** 迭代法反轉單鏈表* 時間復雜度：O(n)，空間復雜度：O(1)** @param head 待反轉鏈表的頭節點* @return 反轉后鏈表的頭節點*/
fun reverseListIterative(head: ListNode?): ListNode? {var prev: ListNode? = null          // 反轉后鏈表的前驅節點var curr: ListNode? = head          // 當前待處理節點while (curr != null) {val nextTemp: ListNode? = curr.next   // 暫存下一個節點curr.next = prev                      // 反轉指向// 向后移動指針prev = currcurr = nextTemp}return prev  // prev 變為新鏈表的頭節點
}

• 關鍵點：

  • nextTemp 用于保護鏈表斷鏈前的下一個節點。
  • 每次循環結束后，prev 節點形成了已反轉部分鏈表。

?? 時間復雜度：需要遍歷一次鏈表，故時間復雜度為 O(n)。

📦 空間復雜度：只使用了常數個指針變量，故空間復雜度為 O(1)。

2.2.3 常見錯誤與調試技巧 🔍

• 忘記更新 curr = nextTemp：導致死循環或指針錯亂。
• 未正確處理 head = null 的情況：輸入空鏈表時，應直接返回 null。
• 書寫 prev = curr; curr = curr.next：在 curr.next 已被修改的情況下會丟失原鏈表結構，所以一定要先保存臨時變量再修改 next。

💡 調試建議：

• 使用示例鏈表手動走一到兩次循環，打印 prev、curr、nextTemp 的值，確保指針指向正確。
• 借助 toString() 方法，將鏈表打印出來，直觀查看節點順序。

---

2.3 遞歸法詳解 ?

2.3.1 解題思路

1. 遞歸終止條件：當 head 為 null 或 head.next == null 時，返回 head（空鏈表或單節點鏈表本身即為反轉結果）。

2. 遞歸過程：

   • 遞歸調用：val newHead = reverseListRecursive(head.next)，反轉后續子鏈表并得到子鏈表的頭節點 newHead。
   • 將 head.next.next = head：即讓后一個節點指向當前節點，實現反轉當前指針。
   • 然后將 head.next = null，切斷當前節點與下一個節點的鏈接，防止形成環。
   • 返回 newHead，逐層回溯即可拼接整個反轉后的鏈表。

2.3.2 Kotlin 實現代碼

/*** 遞歸法反轉單鏈表* 時間復雜度：O(n)，空間復雜度：O(n)（遞歸棧深度）** @param head 待反轉鏈表的頭節點* @return 反轉后鏈表的頭節點*/
fun reverseListRecursive(head: ListNode?): ListNode? {// 遞歸終止：空鏈表或單節點鏈表if (head == null || head.next == null) {return head}// 遞歸反轉后續節點val newHead: ListNode? = reverseListRecursive(head.next)// 反轉當前節點指向head.next?.next = headhead.next = nullreturn newHead
}

• 關鍵點：

  • 遞歸過程中，newHead“沉淀”了整個已經反轉的鏈表頭部；
  • 反轉當前節點需先讓 head.next.next = head，再將 head.next = null 防止環。

?? 時間復雜度：遞歸遍歷一次鏈表，O(n)。

📦 空間復雜度：需要遞歸調用棧，最壞情況遞歸深度為 n，空間復雜度為 O(n)。

2.3.3 迭代 vs 遞歸對比 💡

特性	迭代法	遞歸法
代碼邏輯	通過指針循環修改，流程清晰	借助系統棧完成后序處理，思維優雅
空間開銷	O(1)	O(n)（遞歸棧）
可讀性	對初學者稍顯繁瑣	邏輯更貼近“后序反轉”思路
實際面試	面試常考迭代解法	部分面試官考察遞歸思維

🎯 最佳實踐建議：

• 在鏈表長度較大、擔心棧溢出的場景下，優先使用迭代法；
• 如果面試官特別強調遞歸思維，可以結合遞歸法展示思考深度；
• 始終注意鏈表為空或單節點鏈表的邊界處理。

---

3. 合并兩個有序鏈表（Merge Two Sorted Lists）🔀

3.1 題目描述與輸入輸出要求（LeetCode 21） 📌

• 題目原文（簡體翻譯）：
  將兩個升序鏈表合并為一個新的升序鏈表并返回，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

• 示例：

  輸入：l1 = 1 -> 2 -> 4, l2 = 1 -> 3 -> 4
  輸出：1 -> 1 -> 2 -> 3 -> 4 -> 4
  

• 思路要點：

  1. 迭代法：使用一個虛擬頭節點（dummy），然后遍歷 l1、l2，每次比較頭節點值，小的節點接到新鏈表后面。
  2. 遞歸法：比較 l1.val 和 l2.val，讓小值節點的 next 指向下一個合并結果，遞歸完成合并。

---

3.2 迭代方案詳解 ?

3.2.1 解題思路

1. 創建一個虛擬頭節點 dummy，并維護指針 tail 始終指向合并鏈表的最后一個節點，初始指向 dummy。

2. 當 l1 != null && l2 != null 時：

   • 若 l1.value <= l2.value，則 tail.next = l1，l1 = l1.next；否則 tail.next = l2，l2 = l2.next。
   • 然后 tail = tail.next，向后移動。

3. 循環結束時，至少有一個鏈表遍歷完，直接將剩余非空鏈表接到 tail.next。

4. 最后返回 dummy.next，即合并后鏈表的頭節點。

3.2.2 Kotlin 實現代碼

/*** 迭代法合并兩個有序鏈表* 時間復雜度：O(n + m)，空間復雜度：O(1)** @param l1 有序鏈表1的頭節點* @param l2 有序鏈表2的頭節點* @return 合并后鏈表的頭節點*/
fun mergeTwoListsIterative(l1: ListNode?, l2: ListNode?): ListNode? {val dummy = ListNode(-1)         // 虛擬頭節點var tail: ListNode? = dummy      // tail 指向當前合并鏈表的尾部var p1 = l1var p2 = l2// 遍歷兩個鏈表，選擇較小節點接到合并鏈表后面while (p1 != null && p2 != null) {if (p1.value <= p2.value) {tail?.next = p1p1 = p1.next} else {tail?.next = p2p2 = p2.next}tail = tail?.next}// 將剩余鏈表接到后面tail?.next = p1 ?: p2return dummy.next // 返回真正的頭節點
}

?? 時間復雜度：遍歷 l1 和 l2 各一次，O(n + m)。

📦 空間復雜度：只使用虛擬頭節點等常數指針，O(1)。

3.2.3 常見錯誤與調試技巧 🔍

• 未使用虛擬頭節點：若直接用 l1 或 l2 作為頭節點，需要額外處理頭節點選取邏輯，代碼會更冗長且容易出錯。
• 忘記處理剩余鏈表：循環結束后，若未將剩余部分接上，可能會丟失節點。
• 代碼中 tail 為空判斷：為了保證安全，可以初始化 tail 為非空（如 dummy 本身），避免 tail?.next 出現 null。

💡 調試建議：

• 打印每次合并后合并鏈表的狀態，確認 tail.next 與 p1/p2 的指向。
• 邊界測試：兩個鏈表有一為空、兩個鏈表長度差距較大等情況。

---

3.3 遞歸方案詳解 ?

3.3.1 解題思路

1. 遞歸終止條件：若 l1 == null，直接返回 l2；若 l2 == null，直接返回 l1。

2. 遞歸合并：比較 l1.value 與 l2.value：

   • 若 l1.value <= l2.value，則 l1.next = mergeTwoListsRecursive(l1.next, l2)，返回 l1。
   • 否則 l2.next = mergeTwoListsRecursive(l1, l2.next)，返回 l2。

3.3.2 Kotlin 實現代碼

/*** 遞歸法合并兩個有序鏈表* 時間復雜度：O(n + m)，空間復雜度：O(n + m)（遞歸棧深度）** @param l1 有序鏈表1的頭節點* @param l2 有序鏈表2的頭節點* @return 合并后鏈表的頭節點*/
fun mergeTwoListsRecursive(l1: ListNode?, l2: ListNode?): ListNode? {if (l1 == null) return l2if (l2 == null) return l1return if (l1.value <= l2.value) {l1.next = mergeTwoListsRecursive(l1.next, l2)l1} else {l2.next = mergeTwoListsRecursive(l1, l2.next)l2}
}

?? 時間復雜度：需要合并兩個鏈表，共訪問所有節點，O(n + m)。

📦 空間復雜度：遞歸調用棧深度最壞為 n + m，故 O(n + m)。

3.3.3 迭代 vs 遞歸對比 💡

特性	迭代法	遞歸法
代碼邏輯	基于虛擬頭節點和指針循環	思想更直觀，直接“拼接后續結果”
空間開銷	O(1)	O(n + m)（系統遞歸棧）
可讀性	邏輯平鋪，需要細心維護指針	較為簡潔，一行代碼思考合并后續
面試考點	通常優先考察迭代法	部分題目鼓勵展示遞歸思維能力

? 最佳實踐建議：

• 如果鏈表長度較大或內存有限，建議使用迭代法；
• 面試若要求「簡潔思路」可以使用遞歸法，但要說明空間瓶頸；
• 任何方案都要注意臨界情況：l1 或 l2 為空。

---

4. 判斷鏈表是否有環（Linked List Cycle）🔄

4.1 題目描述與兩種場景（LeetCode 141 & 142） 📌

1. LeetCode 141：判斷鏈表是否有環（Has Cycle）

   • 題目：給定一個鏈表的頭節點 head，判斷鏈表中是否存在環。如果鏈表中存在環，則返回 true；否則返回 false。

   • 示例：

     輸入：head = [3,2,0,-4]，其中 -4 的 next 指向 2，形成環
     輸出：true
     

2. LeetCode 142：環形鏈表 II（Linked List Cycle II）

   • 題目：在已經確認存在環的鏈表中，返回環的入口節點；如果不存在環，返回 null。

   • 示例：

     輸入：head = [3,2,0,-4]，其中 -4 的 next 指向 2
     輸出：指向值為 2 的節點
     

• 思路要點：

  • 判斷是否有環：經典快慢指針（Floyd 判圈法），快指針每次移動兩步，慢指針每次移動一步，如果快慢指針相遇，則存在環；否則不存在。
  • 查找入環節點：當快慢指針相遇后，讓其中一個指針回到鏈表頭部，然后兩個指針都以一步步的速度同時前進，再次相遇的節點即為入環點。

---

4.2 判斷鏈表是否有環（LeetCode 141） ?

4.2.1 解題思路

1. 初始化兩個指針：

   • slow = head 每次走一步
   • fast = head 每次走兩步

2. 進入循環，條件為 fast != null && fast.next != null：

   • slow = slow.next
   • fast = fast.next.next
   • 如果在任意時刻 slow == fast，則代表有環，直接返回 true。

3. 循環結束（fast == null 或 fast.next == null），說明遍歷到鏈表尾部，未形成環，返回 false。

4.2.2 Kotlin 實現代碼

/*** 判斷鏈表是否有環（快慢指針法）* 時間復雜度：O(n)，空間復雜度：O(1)** @param head 鏈表頭節點* @return 如果存在環則返回 true，否則 false*/
fun hasCycle(head: ListNode?): Boolean {var slow: ListNode? = headvar fast: ListNode? = headwhile (fast != null && fast.next != null) {slow = slow?.nextfast = fast.next?.nextif (slow == fast) {return true}}return false
}

?? 時間復雜度：在最壞情況下，需要遍歷鏈表 O(n)。

📦 空間復雜度：只使用常數指針，O(1)。

4.2.3 常見錯誤與調試技巧 🔍

• fast.next.next 空指針風險：在判斷循環條件時必須先確保 fast != null && fast.next != null，否則調用 fast.next.next 會拋出空指針異常。

• 未考慮單節點或空鏈表：若 head == null 或 head.next == null，直接返回 false。

• 調試建議：

  • 在鏈表沒有環、環在不同位置的情況下分別測試；
  • 使用小長度鏈表（如 1、2 個節點）保證邊界條件正確。

---

4.3 查找環的入口節點（LeetCode 142） ?

4.3.1 解題思路

1. 快慢指針相遇：與判斷環相同的步驟，先用快慢指針判斷是否有環。如果沒有環，直接返回 null。
2. 找到相遇節點后：令 ptr1 = head，ptr2 = slow（或 fast，因為 slow == fast）。
3. 同時移動 ptr1 和 ptr2，每次都走一步，直到 ptr1 == ptr2。此時相遇點即為環的入口節點。

🔍 數學證明簡述：

• 設鏈表從頭節點到入環節點的距離為 F，入環節點到相遇節點的距離為 a，相遇節點到入環節點再繞一圈的距離為 b。
• 快指針走過的距離 = 慢指針走過的距離的 2 倍：2(F + a) = F + a + b + a，整理可得 F = b。
• 因此，當相遇后，讓一個指針從頭走 F 步，讓另一個指針從相遇點走 b 步，便會在入環處相遇。

4.3.2 Kotlin 實現代碼

/*** 查找鏈表環的入口節點* 時間復雜度：O(n)，空間復雜度：O(1)** @param head 鏈表頭節點* @return 入環節點，如果無環則返回 null*/
fun detectCycle(head: ListNode?): ListNode? {var slow: ListNode? = headvar fast: ListNode? = head// 1. 判斷是否有環while (fast != null && fast.next != null) {slow = slow?.nextfast = fast.next?.nextif (slow == fast) {// 2. 相遇后，讓 ptr1 從頭開始，ptr2 從相遇點開始var ptr1: ListNode? = headvar ptr2: ListNode? = slowwhile (ptr1 != ptr2) {ptr1 = ptr1?.nextptr2 = ptr2?.next}return ptr1 // 入環節點}}return null
}

?? 時間復雜度：O(n)（一次判斷環 + 再次尋找入口，一共遍歷不超過 2n）。

📦 空間復雜度：O(1)。

4.3.3 調試與注意事項 🔍

• 確認相遇時的指針位置：確保在 slow == fast 時跳出循環，直接進入尋找入口的邏輯。
• 單節點環：若鏈表僅一個節點且自環（即 head.next = head），slow 與 fast 在第一步就會相遇，檢測并返回當前節點。
• 無環鏈表：fast 或 fast.next 為 null 時退出循環，直接返回 null。

🎓 面試拓展建議：

• 了解「龜兔賽跑」判圈思路背后的數學證明；
• 熟悉變形題：如何判斷雙向鏈表、循環鏈表等特殊鏈表的環信息；
• 掌握 Floyd 判圈法的原理，便于靈活應用到其他鏈表相關場景。

---

5. 其他常見鏈表題目匯總與進階分析 📚

在面試與實際開發中，除了上述經典題目，還有許多與鏈表相關的常見題型。下文將對幾道較具代表性的題目進行簡要說明，并給出 Kotlin 代碼示例、復雜度分析及面試提示。

---

5.1 鏈表中間節點（Middle of the Linked List，LeetCode 876） ?

5.1.1 題目描述

給定一個頭結點為 head 的非空單鏈表，返回鏈表的 中間節點。如果有兩個中間節點，則返回第二個中間節點。

• 示例：

  輸入：1 -> 2 -> 3 -> 4 -> 5
  輸出：3 （中間節點值為 3）輸入：1 -> 2 -> 3 -> 4 -> 5 -> 6
  輸出：4 （返回第二個中間節點）
  

5.1.2 解題思路

• 使用 快慢指針：slow 每次走一步，fast 每次走兩步，當 fast 到達鏈表尾部或 fast.next == null 時，slow 恰好指向中間節點。

5.1.3 Kotlin 實現代碼

/*** 返回鏈表中間節點* 時間復雜度：O(n)，空間復雜度：O(1)** @param head 鏈表頭節點* @return 中間節點*/
fun middleNode(head: ListNode?): ListNode? {var slow: ListNode? = headvar fast: ListNode? = headwhile (fast != null && fast.next != null) {slow = slow?.nextfast = fast.next?.next}return slow
}

?? 時間復雜度：O(n)，空間復雜度：O(1)。

🎓 面試提示：

• 注意偶數長度鏈表返回第二個中間節點的要求；
• 如果想返回第一個中間節點，可在循環條件中修改為 while (fast?.next?.next != null)。

---

5.2 刪除倒數第 N 個節點（Remove Nth Node From End of List，LeetCode 19） ?

5.2.1 題目描述

給定一個鏈表，刪除鏈表的倒數第 n 個節點，并返回鏈表的頭節點。

• 示例：

  輸入：head = [1,2,3,4,5], n = 2
  輸出：[1,2,3,5]
  

5.2.2 解題思路

• 使用 雙指針：

  1. 創建虛擬頭節點 dummy，令 first = dummy，second = dummy。
  2. first 先向前移動 n + 1 步，這樣 first 與 second 之間相隔 n 個節點。
  3. 然后同時移動 first、second，直到 first == null。此時 second 指向的是待刪除節點的前一個節點。
  4. 執行 second.next = second.next?.next，完成刪除。

5.2.3 Kotlin 實現代碼

/*** 刪除鏈表倒數第 n 個節點* 時間復雜度：O(n)，空間復雜度：O(1)** @param head 鏈表頭節點* @param n   倒數第 n 個* @return 刪除節點后的鏈表頭*/
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {val dummy = ListNode(-1).apply { next = head }var first: ListNode? = dummyvar second: ListNode? = dummy// first 先移動 n+1 步repeat(n + 1) {first = first?.next}// 同時移動直到 first 為空while (first != null) {first = first.nextsecond = second?.next}// 刪除 second.next 節點second?.next = second?.next?.nextreturn dummy.next
}

?? 時間復雜度：一共遍歷鏈表約兩次，O(n)。

📦 空間復雜度：O(1)。

🎓 面試提示：

• 注意 n 等于鏈表長度時需要刪除頭節點，通過虛擬頭節點可統一處理；
• repeat(n + 1) 中一定要小心邊界，保證 first 挪動到正確位置。

---

5.3 鏈表排序（Sort List，LeetCode 148） ?

5.3.1 題目描述

在 O(n log n) 時間復雜度和 常數級 空間復雜度下，對鏈表進行排序。

• 示例：

  輸入：head = [4,2,1,3]
  輸出：[1,2,3,4]
  

5.3.2 解題思路

• 本題要求 O(n log n) 時間和常數空間，常用思路是 歸并排序（Merge Sort）：

  1. 將鏈表二分為左右兩部分，中間點可使用快慢指針找到。
  2. 遞歸排序左右兩部分。
  3. 合并兩個有序鏈表，返回合并結果。

5.3.3 Kotlin 實現代碼

/*** 歸并排序實現鏈表排序* 時間復雜度：O(n log n)，空間復雜度：O(log n)（遞歸棧深度）** @param head 鏈表頭節點* @return 排序后鏈表的頭節點*/
fun sortList(head: ListNode?): ListNode? {// 遞歸結束：空鏈表或單節點鏈表if (head == null || head.next == null) return head// 1. 使用快慢指針找到中間節點var slow: ListNode? = headvar fast: ListNode? = head.nextwhile (fast != null && fast.next != null) {slow = slow?.nextfast = fast.next?.next}// slow 指向左半部分尾節點val mid: ListNode? = slow?.nextslow?.next = null  // 切斷鏈表// 2. 遞歸排序左右兩部分val left: ListNode? = sortList(head)val right: ListNode? = sortList(mid)// 3. 合并兩個有序鏈表return mergeTwoListsIterative(left, right)
}

?? 時間復雜度：每次將鏈表對半分，遞歸深度為 O(log n)，每層合并時間為 O(n)，總計 O(n log n)。

📦 空間復雜度：歸并排序需要遞歸調用棧，深度約為 O(log n)，滿足題目「常數級空間」的要求（不計遞歸棧）。

---

5.4 鏈表相交（Intersection of Two Linked Lists，LeetCode 160） ?

5.4.1 題目描述

編寫一個程序，找到兩個單鏈表相交的起始節點。如果兩個鏈表沒有交點，返回 null。

• 示例：

  輸入：listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]
  輸出：相交節點值為 8
  

5.4.2 解題思路

• 雙指針法（A/B 路徑交換法）：

  1. 初始化兩個指針 pA = headA, pB = headB。
  2. 同時向后遍歷，當 pA 到達末尾時，讓其重定位到 headB；當 pB 到達末尾時，讓其重定位到 headA。
  3. 如果兩鏈表相交，會在第二次遍歷中同步到交點；如果不相交，最終 pA、pB 都會到達 null，跳出循環。

• 理由：兩指針分別走過 A->B 和 B->A 兩段路徑，路徑長度相同，如果存在交點，則能同步到達；否則同時到達 null。

5.4.3 Kotlin 實現代碼

/*** 查找兩個鏈表相交的起始節點* 時間復雜度：O(n + m)，空間復雜度：O(1)** @param headA 鏈表 A 的頭節點* @param headB 鏈表 B 的頭節點* @return 相交起始節點，如果無交點則返回 null*/
fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {if (headA == null || headB == null) return nullvar pA: ListNode? = headAvar pB: ListNode? = headBwhile (pA != pB) {pA = if (pA == null) headB else pA.nextpB = if (pB == null) headA else pB.next}return pA
}

?? 時間復雜度：O(n + m)。

📦 空間復雜度：O(1)。

🎓 面試提示：

• 要清楚「路徑交換」原理，并能畫圖輔助說明；
• 如果鏈表長度相差特別多，仍然可以保證在第二次遍歷時同步到交點；
• 對自己寫的代碼進行空鏈表、無交點、相交點在第一個節點等邊界測試。

---

5.5 K 個一組翻轉鏈表（Reverse Nodes in k-Group，LeetCode 25） ?

5.5.1 題目描述

給你一個鏈表，每 k 個節點一組進行翻轉，請返回翻轉后的鏈表。

• 如果節點總數不是 k 的整數倍，那么將最后剩余節點保持原有順序。

• 你只能使用常數額外空間。

• 不能只是單純改變節點內部的值，需要進行節點交換。

• 示例：

  輸入：head = [1,2,3,4,5], k = 2
  輸出：[2,1,4,3,5]輸入：head = [1,2,3,4,5], k = 3
  輸出：[3,2,1,4,5]
  

5.5.2 解題思路

1. 使用虛擬頭節點 dummy 指向 head，并維護 groupPrev = dummy。

2. 在循環中，先檢查從 groupPrev 開始是否有 k 個節點，如果不足 k 個，則跳出循環（剩余節點不翻轉）。

3. 若有 k 個節點，將這 k 個節點反轉：

   • 令 groupEnd = groupPrev，向后移動 k 步，找到這組最后一個節點。
   • 記錄下一組的起始節點 nextGroupHead = groupEnd.next。
   • 然后調用 reverse(groupPrev.next, groupEnd) 將當前組內的節點反轉回來，并返回翻轉后的新頭和新尾。
   • 將 groupPrev.next 指向翻轉后這一組的新頭，將新尾的 next 指向 nextGroupHead。
   • 更新 groupPrev = newTail，進入下一輪循環。

4. 輔助函數 reverse(start, end)：反轉從 start 到 end（包含）的子鏈表，并返回翻轉后新的頭和尾。

5.5.3 Kotlin 實現代碼

/*** K 個一組翻轉鏈表* 時間復雜度：O(n)，空間復雜度：O(1)** @param head 鏈表頭節點* @param k    每組節點數* @return 翻轉后鏈表頭節點*/
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {val dummy = ListNode(-1).apply { next = head }var groupPrev: ListNode? = dummy// 輔助函數：判斷從 node 開始是否還有 k 個節點fun hasKNodes(node: ListNode?, k: Int): Boolean {var curr = nodevar count = 0while (curr != null && count < k) {curr = curr.nextcount++}return count == k}// 輔助函數：反轉從 start 到 end 的子鏈表，返回新的頭和尾fun reverseSubList(start: ListNode?, end: ListNode?): Pair<ListNode?, ListNode?> {var prev: ListNode? = end?.nextvar curr: ListNode? = startwhile (prev != end) {val nextTemp = curr?.nextcurr?.next = prevprev = currcurr = nextTemp}return Pair(end, start) // 翻轉后，新頭為 end，新尾為 start}while (true) {// 檢查是否還有 k 個節點val kth = groupPrev?.nextif (!hasKNodes(kth, k)) break// 找到這一組的末尾節點var groupEnd = groupPrevrepeat(k) {groupEnd = groupEnd?.next}// 記錄下一組的頭節點val nextGroupHead = groupEnd?.next// 反轉當前組節點val (newHead, newTail) = reverseSubList(groupPrev?.next, groupEnd)// 連接前后節點groupPrev?.next = newHeadnewTail?.next = nextGroupHead// 更新 groupPrev，進入下一組groupPrev = newTail}return dummy.next
}

?? 時間復雜度：每個節點最多被遍歷一次，O(n)。

📦 空間復雜度：只使用常數級的指針，O(1)。

5.5.4 面試拓展與變形題 🎓

• 變形：如果不能借助輔助函數判斷 hasKNodes，如何在遍歷過程中找到剩余節點不足 k 的情況？
• 變形：如果要返回反轉次數或者部分翻轉（如只反轉前 m 個節點），如何修改算法？
• 搭配題目：Reverse Linked List II（反轉鏈表的部分區間），與 reverseKGroup 思路相似。

---

5.6 Kotlin 中鏈表操作的最佳實踐 ??

1. 可空類型與非空斷言

   • 鏈表節點的 next 多使用 ListNode?，操作時盡量使用 ?.let { } 或 ?: 進行安全判斷，減少 !! 的使用。

   • 示例：

     var curr: ListNode? = head
     while (curr != null) {// ... 直接使用 curr.value 或 curr.next，而非 curr!!.valuecurr = curr.next
     }
     

2. 使用虛擬頭節點（Dummy Node）

   • 在插入、刪除、合并、翻轉等場景下，使用虛擬頭節點可以避免處理頭節點的特殊邏輯，代碼更清晰易維護。

3. 適當封裝常用函數

   • 如 getLength(head)、printList(head)、mergeTwoLists 等基礎操作，可在項目中復用，提升開發效率。

4. 鏈表調試技巧

   • 自定義 toString()：為 ListNode 增加擴展函數，方便打印整個鏈表：

     fun ListNode?.toListString(): String {val sb = StringBuilder()var curr = thiswhile (curr != null) {sb.append(curr.value).append("->")curr = curr.next}sb.append("null")return sb.toString()
     }
     // 使用示例： println(head.toListString())
     

   • 使用測試用例覆蓋邊界情況：空鏈表、單節點鏈表、循環鏈表、鏈表長度不滿足要求等。

5. 時間復雜度與空間復雜度權衡

   • 在鏈表場景中，盡量使用 O(1) 的輔助空間（指針變量）完成操作；
   • 若題目允許，可結合額外數據結構（如棧、哈希表）進行優化或簡化思路（但要注意空間開銷）。

---

6. 總結與最佳實踐建議 🎯

經過以上對鏈表基礎概念與多個經典題目的詳解，我們對鏈表這一數據結構在 Android Kotlin 開發中的應用與算法思路已有了系統性的認識。最后總結如下要點，并給出一些面試與項目實踐的最佳實踐建議：

1. 掌握鏈表基礎：

   • 深刻理解鏈表節點（ListNode）的定義與指針指向，熟悉在 Kotlin 中使用可空類型 (ListNode?) 處理索引與空指針。
   • 熟悉常見操作：遍歷、插入、刪除、獲取長度。

2. 經典題目訓練：

   • 反轉鏈表：迭代和遞歸兩種實現方式，掌握思路與邊界處理。
   • 合并有序鏈表：虛擬頭節點 + 雙指針遍歷。
   • 判斷鏈表是否有環 & 查找入環節點：Floyd 快慢指針判圈與入環算法。
   • 中間節點、刪除倒數第 N 個節點：雙指針技巧，掌握「一次遍歷」、「虛擬頭節點」的應用。
   • K 個一組翻轉、鏈表排序、鏈表相交：歸并排序、路徑交換法、子鏈表翻轉等進階技巧。

3. 代碼實現與復雜度分析：

   • 每種算法都需在代碼中標明時間復雜度、空間復雜度，讓面試官或團隊成員一目了然。
   • 理解遞歸與迭代的空間開銷差異，熟悉 Kotlin 中的尾遞歸優化（tailrec，但在鏈表反轉中不常用）。

4. 面試心得與常見陷阱：

   • 一定要考慮 空鏈表、單節點鏈表、長度不足、環形鏈表 等邊界情況，最好能畫圖模擬指針移動。
   • 注意操作順序：在反轉、刪除操作中要先保存下一個節點，才能安全修改指針；
   • 勤做手寫：在關鍵節點處寫注釋、畫圖，便于溝通解題思路。

5. 項目實踐與性能優化：

   • 在實際 Android 應用中，鏈表場景較少直接手寫，一般使用 List、MutableList 或第三方庫。如果確有特殊需求（如內存受限的隊列實現），可自行實現鏈表。
   • 如果鏈表節點較多，鏈表反復操作可能會造成大量對象創建與垃圾回收，需謹慎評估性能開銷。
   • 在 JNI 或 NDK 場景下，也可能用鏈表結構進行性能密集計算，需要根據具體場景選擇最優實現。

---

面試拓展建議與變形題提示 🎓

• 拓展思路：將單鏈表的算法遷移到 雙向鏈表、循環鏈表，理解指針變化的不同。

• 變形題目示例：

  1. 在環形鏈表中，如何判斷環長度？
  2. 判斷兩個鏈表交點的另一種方法：先計算長度差，再同步移動。
  3. 使用棧結構實現鏈表反轉輸出，不修改鏈表結構。
  4. 多指針技巧：如刪除鏈表中指定值所有節點、合并 K 個有序鏈表（使用堆優化）。

• 現場白板思維：面試時要隨時在白板畫出指針的初始位置、每次移動后的位置，以及邊界條件，幫助面試官理解你的思路。