前言 😊

在 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 个有序链表（使用堆优化）。

• 现场白板思维：面试时要随时在白板画出指针的初始位置、每次移动后的位置，以及边界条件，帮助面试官理解你的思路。