Floyd循环检测算法 快慢指针的三个例子

算法概述

Floyd循环检测算法，也被称为龟兔赛跑算法，或者快慢指针，是一种可以在链表或数组等线性结构中使用的技术。

此技术通过同时使用两个指针，一个快指针和一个慢指针来遍历一个数据结构。通常来说，快指针每次移动两个节点，而慢指针每次只移动一个节点。

它的主要优点是它可以在单次遍历中解决以上的问题，从而使得算法效率高。

在使用快慢指针时，通常需要注意的是可能出现的边界条件，例如链表为空或只有一个或两个节点的情况。

三个例子

1. 找到链表的中点

首先创建两个指针，slowPtr和fastPtr，都初始化为头节点。

然后，只要fastPtr和fastPtr.next不为null，就将fastPtr向前移动两个节点，slowPtr向前移动一个节点。

当fastPtr无法再前进时，slowPtr将位于链表的中点。

Java实现：

class Node {
    int data;
    Node next;
  
    Node(int data) {
        this.data = data;
        next = null;
    }
}

public Node findMiddle(Node head) {
    Node slowPtr = head;
    Node fastPtr = head;
  
    if (head != null) {
        while (fastPtr != null && fastPtr.next != null) {
            fastPtr = fastPtr.next.next;
            slowPtr = slowPtr.next;
        }
    }
  
    return slowPtr;
}

2. 检测链表中是否有环

首先创建两个指针，slow和fast。slow指针每次移动一个节点，fast指针每次移动两个节点。

如果在某个时刻，slow和fast指向同一节点，那么链表中存在环。

如果fast指针到达链表的末尾（即fast或fast.next为null），那么链表中不存在环。

Java实现：

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        next = null;
    }
}

public boolean hasCycle(Node head) {
    if (head == null) {
        return false;
    }

    Node slow = head;
    Node fast = head.next;

    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }

    return true;
}

3. 找到两个链表的交叉点

找到两个链表交叉点通常包括3个步骤：

1. 我们将遍历两个链表以确定他们的长度及是否相交。
2. 我们将使两个指针同时从两个链表的头部开始，但是较长的那个链表的指针会先移动“长度差”的步数。
3. 两个指针将同时移动，当他们相遇时，那个点就是链表的交叉点。

Java实现：

  static class ListNode {
        int data;
        ListNode next;

        ListNode(int data) {
            this.data = data;
            next = null;
        }
    }

    public ListNode getIntersectionListNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode p1 = headA;
        ListNode p2 = headB;

        int length1 = 1;
        int length2 = 1;

        // 两个指针移动到尾部
        while (p1.next != null) {
            p1 = p1.next;
            length1++;
        }
        while (p2.next != null) {
            p2 = p2.next;
            length2++;
        }

        // 如果尾部不同, 则无交叉点
        if (p1 != p2) return null;

        // 将两个指针移动到头部
        p1 = headA;
        p2 = headB;

        // 较长的指针先走一段
        int diff = length1 - length2;
        if (diff > 0) {
            for (int i = 0; i < diff; i++) {
                p1 = p1.next;
            }
        } else if (diff < 0) {
            for (int i = diff; i < 0; i++) {
                p2 = p2.next;
            }
        }

        // 两个指针同时移动, 直到他们相遇
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p1;
    }