想法一
由环形链表题中，沿用快慢指针思想，再结合以下结论
https://blog.csdn.net/2301_79188764/article/details/134299433
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { struct ListNode *meet = slow; while (head != meet) { head = head->next; meet = meet->next; } return meet; } } return NULL; }
结论分析和推导
好像分析的很对，是吧？但是，很遗憾的告诉你，这个推论是错的！
这样，推论才是对的，前面只是特殊情况，刚好符合结论而已
想法二
将链表的环切断，转换为链表相交问题
https://blog.csdn.net/2301_79188764/article/details/134298439
思路比较简单，没有用数学结论，但是代码比较长
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *tail1 = headA, *tail2 = headB; int len1 = 1, len2 = 1; while (tail1->next) { tail1 = tail1->next; len1++; } while (tail2->next) { tail2 = tail2->next; len2++; } if (tail1 != tail2) { return NULL; } int gap = abs(len1 - len2); struct ListNode *longlist = headA, *shortlist = headB; if (len1 < len2) { longlist = headB; shortlist = headA; } while (gap--) { longlist = longlist->next; } while (longlist != shortlist) { longlist = longlist->next; shortlist = shortlist->next; } return longlist; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { struct ListNode *meetNext = slow->next; slow->next = NULL; return getIntersectionNode(head, meetNext); } } return NULL; }
