题解 | #链表中环的入口节点#(快慢指针且相遇到入口长度 +k圈=开始到入口长度 )

链表中环的入口节点

http://www.nowcoder.com/practice/6e630519bf86480296d0f1c868d425ad

图片说明

  • 设置两个指针一个快指针每次走两步(fast->next->next),一个慢指针一次走一步(low->next)。
  • 如果链表中没有环它们最后肯定不相遇,反之它们一定会在环中相遇。
  • 如上图链表中有环,从x点出发,环的入口为点y,它们最后会在z点相遇。
    • 设x到y长度为a,y到z的长度为b,z到y的长度为c,快指针在环中绕了k圈,在k+1圈与慢指针相遇。
    • 慢指针走了a + b的长度,快指针走了 a + k(b + c) + b ,
      因为快指针每次走的是慢指针的两倍。
      则 2*(a + b)= a + k(b + c) + b 。
      化简 得 a = (k-1)(b + c) + c。
    • 即x到y的长度 = k-1圈环的长度 + z到y的长度。即当一个指针从头x开始走,另一个指针从相遇点z开始走,当它们相遇时候一定是在环的入口y。
/**

2*(a + b) = a + k*(b+c) + b
a = (k-1)*(b +c) +c
当指针从头开始,走到环的入口刚好等于另一个指针从相遇位置走(k-1)圈 到达 环入口

 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast,*low;
        low = fast = head;
        bool noRing = true; // 是否存在环
        while(fast && fast->next){ // NULL->next 会报错
            low = low->next;
            fast = fast->next->next;
            if(low == fast) {
                noRing = false; // 有环
                break;
            }
        }
        if(noRing) return NULL; // 没有环 返回
        fast = head;
        while( fast != low){
            fast = fast->next;
            low = low->next;
        }
        return fast;
    }
};

全部评论

相关推荐

努力成为C语言高手:质疑大祥老师,理解大祥老师,成为大祥老师
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务