【算法面试必刷Java版七】链表中环的入口结点

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

    

🚴🏻‍♂️个人主页：莫逸风

    

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

    

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：链表中环的入口结点

描述：

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n=≤10000，1<=结点值<=10000

要求：空间复杂度 O(1)，时间复杂度 O(n)

思路一：应用题（想不到，看题解才看明白）

三个关键点：

fast比slow多走了一半：f = 2s。

fast比slow多走了n圈：f = nb+s。

到达开始节点的表达式为：a+kb。

由上面可知s = nb，即从相遇点到入口节点为a，从头节点到入口节点为a，fast指向头结点，slow指向相遇节点，一步一步后移，再次相遇即为入口节点。

思路二：（投机取巧-不可取）

节点范围是1-10000，遍历链表把节点值减去20000，遍历过的节点都会变为负数，遇到Null返回，遇到负数加20000返回。

代码：

/**
 * 投机取巧
 * @param pHead
 * @return
 */
public ListNode EntryNodeOfLoop(ListNode pHead) {
    ListNode cur = pHead;
    while (cur != null && cur.next != null) {
        if (cur.next.val < 0) {
            cur.next.val = cur.next.val + 20000;
            return cur.next;
        }
        cur.val = cur.val - 20000;
        cur = cur.next;
    }
    return null;
}

/**
 * 快慢指针
 * @param pHead
 * @return
 */
public ListNode EntryNodeOfLoop2(ListNode pHead) {
    // 是否有环
    ListNode listNode = hasCycle(pHead);
    if (listNode==null) return null;
    ListNode fast = pHead;
    ListNode slow = listNode;
    while (true){
        if (fast==slow){
            return fast;
        }
        fast = fast.next;
        slow = slow.next;
    }
}

/**
 * 是否有环
 * @param head
 * @return
 */
public ListNode hasCycle(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast==slow){
            return fast;
        }
    }
    return null;
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：[牛客网面试必刷TOP101](