Leetcode如何找到链表形成环的第一个节点？

本文共计399个文字，预计阅读时间需要2分钟。

力扣链接+思路一：快慢指针法+一个指针从相遇点走，一个指针从起点走，会在入口点相遇.+最终代码：+/+/*+*+Definition+for+singly-linked+list.+*+struct+ListNode+%7B+*+int+val%3B+*+struct+ListNode+%2Anext%3B+*+%7D%3B+*/+

力扣链接

思路一:快慢指针法

一个指针从相遇点走,一个指针从起始点走,会在入口点相遇.

最终代码:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow,* fast; fast = slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { struct ListNode* meet = slow; struct ListNode* start = head; while(meet != start) { meet = meet->next; start = start->next; } return meet; } } return NULL; }

思路二:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ //两个链表的交点 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* tailA = headA,* tailB = headB; int lenA = 1, lenB = 1; while(tailA->next) { tailA = tailA->next; ++lenA; } while(tailB->next) { tailB = tailB->next; ++lenB; } if(tailA != tailB) { return NULL; } int gap = abs(lenA - lenB); struct ListNode* longList = headA,* shortList = headB; if(lenA<lenB) { 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,* fast; fast = slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { //转换成lt1和lt2求交点 struct ListNode* meet = slow; struct ListNode* lt1 = meet->next; meet->next = NULL; struct ListNode* lt2 = head; return getIntersectionNode(lt1,lt2); } } return NULL; }