AcWing 34. 链表中环的入口结点
原题链接
中等
作者:
daniellee
,
2019-04-10 21:14:49
,
所有人可见
,
阅读 971
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
if(head==NULL) return NULL;
if(head->next==head) return head;
if (head->next==NULL || head->next->next==NULL) return NULL;
ListNode* slow = head->next;
ListNode* fast = head->next->next;
// int k=1;
// while(slow!=NULL){
// //cout<<(slow->val)<<endl;
// slow = slow->next;
// k++;
// }
// int n=1;
// slow = head;
while((slow)!=(fast) && fast!=NULL) {
// cout<<(slow->val)<<" "<<(fast->val)<<endl;
slow = slow->next;
// if (fast->next=NULL)
fast = fast->next;
// cout<<fast<<endl;
if (fast->next==NULL) return NULL;
fast = fast->next;
// cout<<fast<<endl;
// n++;
}
// cout<<(slow->val)<<" "<<(fast->val)<<endl;
// if (n==k||fast==NULL) return NULL;
slow = head;
while((fast)!=(slow)){
fast = fast->next;
slow = slow->next;
}
return slow;
}
};