环形链表

解题思路

定义两个指针，一个快指针，一个慢指针，快指针每次移动两个节点，慢指针每次移动一个节点。
从头节点开始，让快慢指针同时移动，如果链表中有环，那么快慢指针一定会在某个节点相遇。
如果快慢指针相遇了，说明链表中有环，返回true。如果快指针移动到了null，说明链表中没有环，返回false。

思考1：为什么快慢指针能判断是否有环

如果链表中没有环，那么快指针会先于慢指针到达链表的尾部，也就是null，这时候我们就可以判断链表中没有环，返回false。
如果链表中有环，那么快指针会在环中不断地追赶慢指针，就像两个人在环形跑道上跑步，速度快的人总会追上速度慢的人。这时候，快指针和慢指针一定会在某个节点相遇，这时候我们就可以判断链表中有环，返回true。
为什么快指针要每次移动两个节点，慢指针要每次移动一个节点呢？这是为了保证快指针和慢指针的相对速度是一定的，如果快指针每次移动三个节点，慢指针每次移动一个节点，那么快指针的速度就是慢指针的三倍，这样可能会导致快指针在环中跳过慢指针，从而无法相遇。如果快指针每次移动一个节点，慢指针每次移动一个节点，那么快指针和慢指针的速度就是一样的，这样也无法相遇。所以，快指针每次移动两个节点，慢指针每次移动一个节点，是一种比较合理的选择，可以保证快慢指针在环中一定会相遇。

代码实现

// 定义一个判断链表是否有环的方法，接受一个头节点作为参数

public boolean hasCycle(Node head) {

    // 如果头节点为空，直接返回false

    if (head == null) {

        return false;

    }

    // 定义快慢指针，初始化为头节点

    Node fast = head;

    Node slow = head;

    // 用一个循环来移动快慢指针

    while (fast != null && fast.next != null) {

        // 快指针每次移动两个节点

        fast = fast.next.next;

        // 慢指针每次移动一个节点

        slow = slow.next;

        // 如果快慢指针相遇了，说明有环，返回true

        if (fast == slow) {

            return true;

        }

    }

    // 如果快指针移动到了null，说明没有环，返回false

    return false;

}

环形链表II

解题思路

定义两个指针，一个快指针fast，一个慢指针slow，都从头节点head开始遍历链表。
快指针每次走两步，慢指针每次走一步，如果链表有环，那么快慢指针一定会在环内相遇，否则快指针会先遍历完链表（遇到null）。
如果快慢指针相遇，说明链表有环，此时将快指针重新指向头节点head，慢指针保持在相遇节点，然后快慢指针都每次走一步，直到再次相遇，相遇的节点就是入环的第一个节点。即：从头节点到入环节点的距离，等于从相遇节点继续走到入环节点的距离。
如果快慢指针没有相遇，说明链表无环，返回null。

举个例子：

  1 -> 2 -> 3 -> 4

       ^         |

       |         v

       7 <- 6 <- 5

这个链表中有一个环，从节点2到节点7。环的长度是6，入口节点是节点2。
我们可以用快慢指针的方法，让快指针从节点1开始，每次走两步，慢指针从节点1开始，每次走一步，它们在节点7相遇，然后让快指针从头开始一步步走，慢指针保持在相遇节点开始一步步走，快慢指针再次在2节点相遇，所以2节点就是入环节点。

思考1：为什么慢指针每次移动一步，快指针每次移动两步，一定会在环中相遇而不是错过？

假设链表的长度是L，环的长度是n，环的入口节点距离头节点的距离是a，快慢指针在环中相遇的节点距离环的入口节点的距离是b，那么有以下关系：

当快慢指针相遇时，慢指针走过的距离是a+b，快指针走过的距离是a+b+k*n，其中k是快指针在环中绕的圈数。
因为快指针的速度是慢指针的两倍，所以快指针走过的距离是慢指针的两倍，即2*(a+b) = a+b+kn，化简得a+b = kn。
这个式子的意思是，当快慢指针相遇时，慢指针走过的距离刚好是环的长度的整数倍，也就是说，慢指针在环中走了k圈，快指针在环中走了k+1圈。
这样，我们可以知道，快慢指针一定会在环中相遇，而不是错过，因为快指针每次都会比慢指针多走一步，所以它们之间的距离每次都会缩小一步，直到相遇为止。

思考2：如何证明，从头节点到入环节点的距离，等于从相遇节点继续走到入环节点的距离？

假设从头结点到环形入口节点的距离为x。环形入口节点到fast指针与slow指针相遇节点距离为y。从相遇节点再到环形入口节点距离为z

当快慢指针首次相遇时，慢指针走过的路程为x + y，快指针走过的路程为x + y + n (y + z)。
由于快指针的速度是慢指针的两倍，所以快指针走过的路程是慢指针的两倍，即(x + y) * 2 = x + y + n (y + z)。
化简得到x + y = n (y + z)，即x = n (y + z) - y，再从n(y+z)中提出一个(y+z)来，得到x = (n - 1) (y + z) + z。而 y + z正好是环一圈的长度。
这个式子的意义是，从头节点到入环节点的距离，等于快慢指针相遇后，一个指针继续走n-1圈，再加上从相遇点到入环节点的距离。
当n=1时，即某一指针只走了一圈，那么x = z，即从头节点到入环节点的距离，等于从相遇节点继续走到入环节点的距离。
因此，如果我们让一个指针从头节点开始，另一个指针从相遇节点开始，每次都走一步，那么他们最终会在入环节点相遇，这样就找到了入环节点。

代码实现

    public ListNode detectCycle(ListNode head) {

        //如果链表为空或只有一个节点，直接返回null

        if (head == null || head.next == null) {

            return null;

        }

        //定义快慢指针

        ListNode fast = head;

        ListNode slow = head;

        //遍历链表，直到快指针遇到null或快慢指针相遇

        while (fast != null && fast.next != null) {

            //快指针走两步，慢指针走一步

            fast = fast.next.next;

            slow = slow.next;

            //如果快慢指针相遇，说明有环

            if (fast == slow) {

                //将快指针重新指向头节点

                fast = head;

                //快慢指针都每次走一步，直到再次相遇

                while (fast != slow) {

                    fast = fast.next;

                    slow = slow.next;

                }

                //返回相遇的节点，即入环的第一个节点

                return fast;

            }

        }

        //如果快指针遇到null，说明无环，返回null

        return null;

    }

巴特西

环形链表I、II（含代码以及证明）

环形链表

解题思路

思考1：为什么快慢指针能判断是否有环

代码实现

环形链表II

解题思路

思考1：为什么慢指针每次移动一步，快指针每次移动两步，一定会在环中相遇而不是错过？

思考2：如何证明，从头节点到入环节点的距离，等于从相遇节点继续走到入环节点的距离？

代码实现

最新文章

热门文章