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

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

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 实现 快慢指针技巧，可以高效解决链表中的常见问题。掌握这一技巧，链表问题将不再是难题！