欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【算法/剑指Offer】给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

程序员文章站 2022-06-17 16:13:35
...

 如果一个链表中有环,那么,我们如何找到这个链表的入口节点呢? 

  思路是这样的:设定两个指针,一个慢指针,一个快指针,快指针的速度是慢指针的两倍,然后呢,如果有环,他们一定会在环中相遇。 

 (1) 如果这时快指针已经是在环里走了一圈了(这种情况对应于非环指针较短的情况),如下所示:

【算法/剑指Offer】给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

根据上图,我们可以得到下面的关系式:

  • w + n + y = 2 (w + y)

   经过化简,我们可以得到:w  = n - y;

      所以,这种情况下,我们就可以直接把p2放在pHead处,然后让两个指针以同样的速度走,那么,两者下一次就一定在入口节点相遇了。

  (2)如果是相遇的时候,p2已经走了很多圈了,思路也是一样的,只是这时的w会更长一点,并且我们可以肯定的是p1肯定不会绕着圈走一圈,即p1只在环上走了y的距离:

  • w + y + kn = 2 (w + y) 

  同样,我们可以推到出来, kn - y = w。 

  然后,这时还是可以将P2放在pHead处,p1在转了n圈之后,也一定会在入口节点和刚刚到来的p2相遇。 

   所以, 最终代码如下所示:

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
    // write code here
    // 使用两个指针,一个快的,一个慢的,快的时慢的两倍,如果有环,那么他么一定会相遇。
    if (pHead == null || pHead.next == null) {
        return null;
    }
    
    var p1 = pHead;
    var p2 = pHead;
    while (p2 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next.next;
        if (p1 == p2) {
            p2 = pHead;
            while (p1 != p2) {
                p1 = p1.next;
                p2 = p2.next;
            }
            if (p1 == p2) {
                return p1;
            }
        }
    }
    return null;
    
}
module.exports = {
    EntryNodeOfLoop : EntryNodeOfLoop
};

###########################################################

链接:https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4
来源:牛客网
这里用到了STL中的set,set有一个特性就是不能插入相同元素,这样只需遍历原List一次就可以判断出有没有环,还有环的入口地址。s.insert(node).second这里在插入的同时也判断了插入是否成功,如果不成功表明set中已经有该元素了,该元素就是环的入口元素。

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        set<ListNode*> s;
        ListNode* node = pHead;
        while(node!=NULL){
            if(s.insert(node).second)
                node = node->next;
            else
                return node;
        }
        return node;
         
    }
};