链表中环的入口点

发表于

描述

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

输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

返回值描述：

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例1

1
2
3
输入:  {1,2},{3,4,5}
返回:  3
说明:  返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3

示例2

1
2
3
输入:  {1},{}
返回:  "null"
说明:  没有环，返回对应编程语言的空结点，后台程序会打印"null"

示例3

1
2
3
输入:  {},{2}
返回:  2
说明:  环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2

题解

快慢指针

通过定义slow和fast指针，slow每走一步，fast走两步，若是有环，则一定会在环的某个结点处相遇（slow == fast）。

从相遇处到入口结点的距离与头结点与入口结点的距离相同。

环的入口

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
package main

type ListNode struct{
    Val int
    Next *ListNode
}

func EntryNodeOfLoop(pHead *ListNode) *ListNode{
    fast := pHead
    slow := pHead

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            fast = pHead
            for fast != slow {
                fast = fast.Next
                slow = slow.Next
            }
            return slow

        }
    }

    return nil
}