数据结构|链表 刷题

给定单链表如果有环的话请返回从头节点进入环的第一个结点思路两个快慢指针p q 求出相遇点然后q从头出发p从相遇点出发同频p q一定会在入环点再次相遇。设环的周长为c数学证明相遇时慢指针 p走了mnc*xx为圈数快指针q走了mnc*yy圈因为快指针速度为慢指针2倍得到等式2*mnc*xmnc*y化简得到mc*y-2x-n当快指针重新指向链表头慢指针在相遇点不动然后两个指针以相同速度前进。快指针走到环入口需要走m的距离而慢指针从相遇点出发因为mnc×(y−2x)所以慢指针走m的距离后也会到达环入口因为m的距离和相遇点到环入口的距离n的关系满足上述等式bool Ifcyclic1(List plist,Node**meet) { if (plist NULL || plist-next NULL) { *meet NULL; return false; } Node* p plist-next; Node* q plist-next-next; while (q ! NULL q-next ! NULL) { if (p q) { *meet p;//得到相遇点 return true; } p p-next; q q-next-next; } *meet NULL; return false; } void Return(List plist, Node* meet, Node** result) { if (plist NULL || plist-next NULL) { *result NULL; return; } Node* p plist-next; Node* q meet; while (p!q) { p p-next; q q-next; } *result p;//得到相遇点 return; } int main() { Node head; InitList(head); for (int i 0; i 10; i) { Insert_tail(head, i); } Show(head); //构造环 Node* q Search(head, 5); Node* s Search(head, 9); if (q ! NULL s ! NULL) { s-next q; } Node* meet; Node* result; if(Ifcyclic1(head, meet)) { Return(head, meet, result); printf(该链表有环,入环的第一个结点为%d\n,result-data); } else { printf(该链表没有环\n); } }