当前位置: 首页 > >

判断链表环的入口

发布时间:

方法一:


使用hash表,遍历链表每一个节点,放入哈希表中,当待放入的节点存在于哈希表中时,这个节点就是环的入口,否则就没有环。


方法二:


假设链表link,


用两个指针,一个fast指针,每次走两步,一个slow指针,每次走一步。


当fast指针与slow指针相遇时,假设fast指针走了2s,那么slow指针走了s


假设链表的长度为L,链表起始点与环的入口距离为a,环的长度为r,环的入口与相遇点的距离为x,


? ? ? ? ? L - a = r,相遇点到环入口的距离为Y =?L-a-x


相遇时fast在环上跑了n圈、slow在环上跑了m圈,其中n-m>=1,那么有等式:


? ? ? ? ? ? ?2s = s + nr可知:s = nr


? ? ? ? ? ? ?s = a+x+mr。


所以:a+x+mr = nr? ? 可得:


==》a+x = (n-m)r?


==》a+x = (n-m-1)r + r,其中r=L-a,


那么:a+x = (n-m-1)r + (L-a)


==》a = (n-m-1)r + (L-a-x)


因为n-m>=1,设z=n-m-1,那么最后的等式:


a = zr + Y


我们将fast重新指向链表入口,每次走一步,slow依旧,那么,两个指针一定会在相遇点相遇


Node *findLoopLinkStart(Node * head){
Node *fast, *slow;
fast = slow = head;
while(slow != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
if (fast == slow) break;
}
if (fast == NULL || slow == NULL){
return NULL;
}
fast = head;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return fast;
}

?



友情链接: