链表中环的入口结点

题目描述

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

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

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

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入描述：

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

返回值描述：

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

示例

示例1

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

示例2

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

示例3

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

代码

代码1 使用哈希法

题解

可以遍历整个链表，每遍历一个节点，就把当前节点保存在Set中，当遍历到某个节点时，其已经在Set中存在了，就说明这个节点是环的开始，即：

遍历单链表的每个结点
如果当前结点地址没有出现在set中，则存入set中
否则，出现在set中，则当前结点就是环的入口结点
整个单链表遍历完，若没出现在set中，则不存在环

代码

function EntryNodeOfLoop(pHead){
    // 声明一个set用来存储已经遍历过的节点
    let linkset = new Set()
    let loopNode = null // 返回的结果
    
    while(pHead){
        // 若果set中已经有这个值了，说明它就是环的起始位置
        if(linkset.has(pHead)){
            loopNode = pHead
            break
        }
        // 挨个遍历
        linkset.add(pHead)
        pHead = pHead.next
    }
    return loopNode
}

代码2 快慢指针法

这个是个定理，有环的链表中，

快满指针都从表头开始

快指针每次走两步，慢指针每次走一步，一定会在环中的某一个节点相遇（第一次相遇）
在第一次相遇点上，将快指针挪至表头重新出发，二者都改为一次一步，下一次两个指针一定会在环口重新相遇（第二次相遇）。

/*
设置 快、慢 指针
	快指针走两步、慢指针走一步
1. 假如有环，一定会相遇于环中的某点（结论1）
2. 接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。
*/
function EntryNodeOfLoop(pHead)
{
    // 如果是空或者一个节点，且没有环，直接返回null
    if(pHead === null || pHead.next ===null){
        return null
    }
    
    let fast = pHead // 快指针 
    let slow = pHead // 满指针 
    
    while(fast){
        fast = fast.next.next // 每次走两步
        slow = slow.next // 每次走一步
        
        // 第一次相遇（结论1）一定会相遇在环的某一点
        if(fast === slow){
            fast = pHead // fast 从链表头从新出来，改为一次走一步
            while(fast !== slow){
                fast = fast.next
                slow = slow.next
            }
            // 第二次相遇，（结论2）一定会在环口相遇
            return fast
        }
    }
}

题目来源

JZ23 链表中环的入口结点

链表中环的入口结点 ​

题目描述 ​

输入描述： ​

返回值描述： ​

示例 ​

代码 ​

代码1 使用哈希法 ​

题解 ​