剑指offer—找出链表环的入口 解答

剑指offer—找出链表环的入口

我们先来看一道判断是否有环的题目

leetcode141—环形链表

题目描述

给定一个链表,判断链表中是否有环。有则返回true,没有则返回false

思路

快慢指针

  • 快指针每次走两步;慢指针每次走一步

如果链表存在环,那么快指针一定会追上慢指针;否则没有环快指针走到链表尽头。

代码

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        if(head==null||head.next==null) return false;
        while(slow!=null&&fast!=null){
            if(fast.next==null) return false;
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow) return true;
        }
        return false;
    }
}

剑指offer—找出链表环的入口

题目描述

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

思路

我们已经知道如何判断是否有环,我们再仔细分析一下

  • 相遇点在哪?

我们不仿画个图分析

首先相遇时一定是慢指针第一次进入环内,我们稍后解释

我们根据上面这个分析可以看到相遇点往前到入口的距离等于头结点到入口点的距离

  • 怎么找到入口?

利用上面这一点我们就可以再使用一个指针从头结点开始与相遇点节点一起移动,最后相遇点就是入口点

  • 为什么遇到的时候一定是第一次?

你可能会想说快慢指针不一定在环内第一圈就相遇了,但是事实就是这样;

  1. 首先我们知道的是慢指针永远无法追上快指针,就像跑步一样,慢的永远追不上快的,但是快的可能追的上慢的;
  2. 因为快指针比慢指针快一倍,所以当慢指针进入环内时,一定能在慢指针走完第一圈时遇到慢指针

可能还有人有疑问觉得,慢指针进入环内第一圈内,快指针一定能遇到吗?

我们做个假设,也就是极端情况,假设慢指针进入环内时,快指针在环内第二个元素(这样一定是两点最远的时候),我们设环长L,慢指针需要走L-1步才下一次进入环,但是快指针只需(L-2)/2次就结束一次环了,它再走一次环的时间加起来也只要L-2次<L-1次,所以一定是可以在慢指针第一次出环前遇到慢指针,按道理,快指针一定也在第二次环内

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        if(head==null||head.next==null) return null;
        while(fast!=null&&slow!=null){
            if(fast.next==null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if(slow==fast) break;
        }
        if(fast!=slow) return null;
        ListNode slow2 = head;
        while(slow2!=slow){
            slow = slow.next;
            slow2 = slow2.next;
        }
        return slow2;
    }
}