剑指Offer_55

发表于 | 分类于

题目

一个链表中包含环，请找出该链表的环的入口结点。

解题思路

参考博客： 点击跳转

解法一：

快慢指针 fast 走2步和 slow 走1步

情况一： 快指针比慢指针只多走了一个环，如下图所示

点击加载

a. 首先找到快慢指针在环中的相遇点

b. 设慢指针走了x步，且环中有n个节点，那么快指针多走一圈的情况下：
2x = n + x，即 n = x

c. 可以看出slow实际走了一个环的步数，再让fast指向链表头部，slow位置不变。

假设链表开头到环接口的距离是y，如下图所示，那么x-y表示slow指针走过的除链表开头y在环中走过的距离，那么slow再走y步，此时fast结点与slow结点相遇，fast == slow ，x-y+y=x = n，即此时slow指向环的入口。

最后，slow在走y步就到环的入口了 x -> n

点击加载

情况二： 当 fast 比 slow 多走n个环

fast比slow多走r圈有2x=rn+x; x=rn

同情况一可得： fast == slow时 ，x-y+y=x = rn，即此时slow指向环的入口。

点击加载 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
 public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode fast = pHead;
        ListNode slow = pHead;
        
        // while循环条件 有环
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            
            if(fast == slow){
                fast = pHead;
                while(fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

解法二：

使用HashSet来判断重复值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.HashSet;
/*
 public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        HashSet<ListNode> hashSet = new HashSet<>();
        while(pHead != null){
            if(hashSet.contains(pHead)){
                return pHead;
            }
            hashSet.add(pHead);
            pHead = pHead.next;
        }
        return pHead;
    }
}