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

时间：2023-02-12 14:06:18

解题思路

  1. 定义两个指针，一个快指针，一个慢指针，快指针每次移动两个节点，慢指针每次移动一个节点。
  2. 从头节点开始，让快慢指针同时移动，如果链表中有环，那么快慢指针一定会在某个节点相遇。
  3. 如果快慢指针相遇了，说明链表中有环，返回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

解题思路

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

相关文章