【刷算法】判断链表是否有环以及返回入环节点

wendux 发布于2019-08-22 18:06 / 2937人阅读

摘要：为什么这么做就可以保证在入环节点相遇证明一下如图，设整个链表长度为，环长度为，且距离具有方向性，例如是点到点的距离，是点到点的距离，。代码实现有环，重新回到链表头和重新相遇时，相遇节点就是入环节点

题目描述

判断一个单链表是否有环，有环则返回入环节点，否则返回null

1->2->3->4->5->6
            ↑  ↓
            8<-7

例如上面这个链表就有环，入环节点是5

判断链表有环

通常判断链表是否有环，会采用快慢指针的方法，其实道理很简单，就像两个人赛跑且一个人跑得快一个人跑得慢。如果赛道是直的，那么快人跑到终点时慢人还未到；如果赛道是环形，则快人和慢人总会相遇。
代码实现

function ListNode(x){
    this.val = x;
    this.next = null;
}
function EntryNodeOfLoop(pHead){
if(pHead === null)
    return null;
// 快慢指针从链表的头部开始
var fast = pHead;
var slow = pHead;

while(fast.next !==null && fast.next.next !== null) {
// 快指针每次走两步；慢指针每次走一步
    slow = slow.next;
    fast = fast.next.next;
    // 快慢指针相遇时，跳出while循环
    if(slow === fast)
        break;
}
// 快指针已经到了链表尾部了还没和慢指针相遇，说明没有环
if(fast === null || fast.next === null)
    return null;
    
// 后续会处理有环的情况...
}

找到入环节点

常见的方法是：在确定链表有环之后，慢指针重新指向链表头，快指针留在相遇处；然后快慢指针再以每次移动1个节点的速度前进，最终他们在入环节点相遇。
为什么这么做就可以保证在入环节点相遇？证明一下：

如图，设整个链表长度为L，环长度为R，且距离具有方向性，例如CB是C点到B点的距离，BC是B点到C点的距离，CB!=BC。当证明有环时，fast和slow都顺时针到了B点，则此时：
slow走的距离：AC+CB
fast走的距离：AC+k*R+CB(k=0,1,2...)
由于fast每次走2个节点，slow每次走1个节点，所以：
2(AC+CB) = AC+k*R+CB
AC+CB = k*R
AC+CB = (k-1)*R+R
AC = (k-1)*R+R-CB
AC = (k-1)*R+BC
从最终的表达式可以看出来，AC的距离等于绕环若干圈后再加上BC的距离，也就是说慢指针从A点出发以速度1前进、快指针从B点出发以速度1前进，则慢指针到C点时，快指针也必然到了。
代码实现：

function ListNode(x){
    this.val = x;
    this.next = null;
}
function EntryNodeOfLoop(pHead){
    if(pHead === null)
        return null;
    var fast = pHead;
    var slow = pHead;

    while(fast.next !==null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast)
            break;
    }

    if(fast === null || fast.next === null)
        return null;
    // 有环，slow重新回到链表头
    slow = pHead;
    
    // slow和fast重新相遇时，相遇节点就是入环节点
    while(slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
}

云服务器 GPU云服务器链表算法链表排序算法算法 c语言链表判断是否

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95503.html

大厂算法面试之leetcode精讲7.双指针

摘要：空间复杂度双指针，循环数组，较小的那个先向内移动如果高的指针先移动，那肯定不如当前的面积大计算面积更新最大面积相交链表方法哈希表思路将链表存入中，第一个相同的节点就是重合的节点复杂度时间复杂度，分别是两个链表的长度。大厂算法面试之leetcode精讲7.双指针视频教程（高效学习）:点击学习目录：1.开篇介绍2...

不知名网友 2021-11-26 11:11 评论0 收藏0
Leetcode：刷完31道链表题的一点总结

摘要：既然说到地址空间了就顺带说一下上面环形链表这道题的另一种很的解法吧。介绍完常规操作链表的一些基本知识点后，现在回到快慢指针。前几天第一次在 Segmentfault 发文—JavaScript：十大排序的算法思路和代码实现，发现大家似乎挺喜欢算法的，所以今天再分享一篇前两个星期写的 Leetcode 刷题总结，希望对大家能有所帮助。本文首发于我的blog 前言今天终于...

DevTalking 2019-08-23 17:50 评论0 收藏0
JAVASCRIPT算法（6）

摘要：还是链表算法题目描述给出两个无环单链表判断和是否相交。所以可以得出另外一种解法，先遍历链表，记住尾节点，然后遍历链表，比较两个链表的尾节点，如果相同则相交，不同则不相交。想法还是奇妙的。算法写起来不难，难的是想到这个。还是链表算法题目描述：给出两个无环单链表A: a1 → a2 ↘ c1 → c2 → c3 → ...

FreeZinG 2019-08-21 17:56 评论0 收藏0
写一段代码判断单向链表中有没有形成环，如果形成环，请找出环的入口处，即P点

摘要：由于要比移动的快，如果有环，一定会先进入环，而后进入环。现在问题就简单了，由于移动的距离永远是的一般，因此当遍历玩整个环长度个节点的时候正好遍历了个节点，也就是说，此时正好指向距离最远的点。首先，关于单链表中的环，一般涉及到以下问题： 1.给一个单链表，判断其中是否有环的存在； 2.如果存在环，找出环的入口点； 3.如果存在环，求出环上节点的个数； 4.如果存在环，求出链表的长度； ...

OldPanda 2019-07-01 13:56 评论0 收藏0