快慢指针【中分链表、判断链表中是否存在环】

一、中分链表：找到链表的中心节点

Java 实现

1. class ListNode {
2.     int val;
3.     ListNode next;
4.     ListNode(int val) {
5.         this.val = val;
6.         this.next = null;
7.     }
8. }
10. public class MiddleOfLinkedList {
11.     public ListNode findMiddleNode(ListNode head) {
12.         if (head == null) {
13.             return null;
14.         }
15.         
16.         ListNode slow = head;
17.         ListNode fast = head;
18.         
19.         // 快指针每次走两步，慢指针每次走一步
20.         while (fast != null && fast.next != null) {
21.             slow = slow.next;
22.             fast = fast.next.next;
23.         }
24.         
25.         // 慢指针指向中间节点
26.         return slow;
27.     }
29.     public static void main(String[] args) {
30.         // 示例链表：1 -> 2 -> 3 -> 4 -> 5
31.         ListNode head = new ListNode(1);
32.         head.next = new ListNode(2);
33.         head.next.next = new ListNode(3);
34.         head.next.next.next = new ListNode(4);
35.         head.next.next.next.next = new ListNode(5);
37.         MiddleOfLinkedList solution = new MiddleOfLinkedList();
38.         ListNode middle = solution.findMiddleNode(head);
39.         System.out.println("中间节点值: " + middle.val); // 输出: 3
40.     }
41. }

复制代码

示例

输入链表：1 -> 2 -> 3 -> 4 -> 5
输出：3
输入链表：1 -> 2 -> 3 -> 4 -> 5 -> 6
输出：4

---

二、判断链表中是否存在环

Java 实现

1. class ListNode {
2.     int val;
3.     ListNode next;
4.     ListNode(int val) {
5.         this.val = val;
6.         this.next = null;
7.     }
8. }
10. public class LinkedListCycle {
11.     public ListNode detectCycle(ListNode head) {
12.         if (head == null || head.next == null) {
13.             return null;
14.         }
15.         
16.         ListNode slow = head;
17.         ListNode fast = head;
18.         
19.         // 判断是否有环
20.         while (fast != null && fast.next != null) {
21.             slow = slow.next;
22.             fast = fast.next.next;
23.             
24.             // 快慢指针相遇，说明有环
25.             if (slow == fast) {
26.                 break;
27.             }
28.         }
29.         
30.         // 无环
31.         if (fast == null || fast.next == null) {
32.             return null;
33.         }
34.         
35.         // 找到环的入口
36.         fast = head;
37.         while (fast != slow) {
38.             fast = fast.next;
39.             slow = slow.next;
40.         }
41.         
42.         return slow;
43.     }
45.     public static void main(String[] args) {
46.         // 示例链表：1 -> 2 -> 3 -> 4 -> 5 -> 2（节点5指向节点2，形成环）
47.         ListNode head = new ListNode(1);
48.         head.next = new ListNode(2);
49.         head.next.next = new ListNode(3);
50.         head.next.next.next = new ListNode(4);
51.         head.next.next.next.next = new ListNode(5);
52.         head.next.next.next.next.next = head.next; // 形成环
54.         LinkedListCycle solution = new LinkedListCycle();
55.         ListNode cycleNode = solution.detectCycle(head);
56.         if (cycleNode != null) {
57.             System.out.println("环的入口节点值: " + cycleNode.val); // 输出: 2
58.         } else {
59.             System.out.println("链表中无环");
60.         }
61.     }
62. }

复制代码

示例

输入链表：1 -> 2 -> 3 -> 4 -> 5 -> 2（节点5指向节点2，形成环）
输出：2
输入链表：1 -> 2 -> 3 -> 4 -> 5
输出：链表中无环

---

三、核心头脑总结

• 快慢指针的速率差：
  
  
  
  • 快指针每次移动两步，慢指针每次移动一步；
    
  • 在中分链表中，快指针到达末端时，慢指针恰恰在中心；
    
  • 在判断环时，快指针会追上慢指针。
    
  
  
• 时间复杂度：
  
  
  
  • 中分链表：O(n)，此中 n 是链表长度；
    
  • 判断环：O(n)，最多遍历链表两次。
    
  
  
• 空间复杂度：O(1)，只使用了常数级别的额外空间。
  

---

四、练习题

• 中分链表：
  
  
  
  • 输入：1 -> 2 -> 3 -> 4 -> 5 -> 6
    
  • 输出：4
    
  
  
• 判断环：
  
  
  
  • 输入：1 -> 2 -> 3 -> 4 -> 5 -> 3（节点5指向节点3，形成环）
    
  • 输出：3
    
  
  

---

通过 Java 实现 快慢指针本领，可以高效办理链表中的常见标题。把握这一本领，链表标题将不再是困难！