一、等分鏈表：找到鏈表的中間節點

Java 實現

class ListNode {int val;ListNode next;ListNode(int val) {this.val = val;this.next = null;}
}public class MiddleOfLinkedList {public ListNode findMiddleNode(ListNode head) {if (head == null) {return null;}ListNode slow = head;ListNode fast = head;// 快指針每次走兩步，慢指針每次走一步while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}// 慢指針指向中間節點return slow;}public static void main(String[] args) {// 示例鏈表：1 -> 2 -> 3 -> 4 -> 5ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);MiddleOfLinkedList solution = new MiddleOfLinkedList();ListNode middle = solution.findMiddleNode(head);System.out.println("中間節點值: " + middle.val); // 輸出: 3}
}

示例

輸入鏈表：1 -> 2 -> 3 -> 4 -> 5
輸出：3

輸入鏈表：1 -> 2 -> 3 -> 4 -> 5 -> 6
輸出：4

---

二、判斷鏈表中是否存在環

Java 實現

class ListNode {int val;ListNode next;ListNode(int val) {this.val = val;this.next = null;}
}public class LinkedListCycle {public ListNode detectCycle(ListNode head) {if (head == null || head.next == null) {return null;}ListNode slow = head;ListNode fast = head;// 判斷是否有環while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;// 快慢指針相遇，說明有環if (slow == fast) {break;}}// 無環if (fast == null || fast.next == null) {return null;}// 找到環的入口fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return slow;}public static void main(String[] args) {// 示例鏈表：1 -> 2 -> 3 -> 4 -> 5 -> 2（節點5指向節點2，形成環）ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);head.next.next.next.next.next = head.next; // 形成環LinkedListCycle solution = new LinkedListCycle();ListNode cycleNode = solution.detectCycle(head);if (cycleNode != null) {System.out.println("環的入口節點值: " + cycleNode.val); // 輸出: 2} else {System.out.println("鏈表中無環");}}
}

示例

輸入鏈表：1 -> 2 -> 3 -> 4 -> 5 -> 2（節點5指向節點2，形成環）
輸出：2

輸入鏈表：1 -> 2 -> 3 -> 4 -> 5
輸出：鏈表中無環

---

三、核心思想總結

1. 快慢指針的速度差：

   • 快指針每次移動兩步，慢指針每次移動一步；
   • 在等分鏈表中，快指針到達末尾時，慢指針正好在中間；
   • 在判斷環時，快指針會追上慢指針。

2. 時間復雜度：

   • 等分鏈表：O(n)，其中 n 是鏈表長度；
   • 判斷環：O(n)，最多遍歷鏈表兩次。

3. 空間復雜度：O(1)，只使用了常數級別的額外空間。

---

四、練習題

1. 等分鏈表：

   • 輸入：1 -> 2 -> 3 -> 4 -> 5 -> 6
   • 輸出：4

2. 判斷環：

   • 輸入：1 -> 2 -> 3 -> 4 -> 5 -> 3（節點5指向節點3，形成環）
   • 輸出：3

---

通過 Java 實現 快慢指針技巧，可以高效解決鏈表中的常見問題。掌握這一技巧，鏈表問題將不再是難題！