struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow = head; struct ListNode* fast = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; if(slow == fast) { struct ListNode* meet = slow; meet = meet->next; slow->next = NULL; //断环 struct ListNode* List1 = head; struct ListNode* List2 = meet; int LenHead = 1; int LenMeet = 1; int gap = 0; while(List1->next) //计算走到尾需要多少步 { ++LenHead; List1 = List1->next; } while(List2->next) { ++LenMeet; List2 = List2->next; } if(List1 == List2) //这里可以不写，因为有相遇点必定是相交链表 { struct ListNode* shortList = head; //先假设头结点到入口点的长度更短 struct ListNode* longList = meet; gap = abs(LenHead-LenMeet); //更长的的先走gap步 if(LenHead > LenMeet) //如果假设错了就交换 { shortList = meet; longList = head; } while(gap--) //让长短链表距离相等 { longList = longList->next; } while(longList != shortList) //相等就说明找到入口点 { longList = longList->next; shortList = shortList->next; } return longList; } } } return NULL; }