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

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

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 -> 5
        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);

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