环形链表

解题思路

  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;
    }
02-21 02:16