Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.
Follow up: Can you solve it without using extra space?
C++
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* detectCycle2(ListNode *head){ ListNode *fast = head; ListNode *slow = head; if(head==NULL) return NULL; while (NULL != fast){ if (fast != NULL) fast = fast->next; if (fast != NULL) fast = fast->next; if (slow != NULL) slow = slow->next; while(fast != NULL && slow == fast){ slow = head; while(slow!=fast){ fast = fast->next; slow = slow->next; } return slow; } } return NULL; } ListNode *detectCycle(ListNode *head) { ListNode *fast = head; ListNode *slow = head; if (NULL == head) return NULL; while(fast && fast->next){ fast = fast->next->next; slow = slow->next; if (fast != NULL && slow == fast) return FindTheFirstSameNode(fast,head); } return NULL; } ListNode *FindTheFirstSameNode(ListNode* head1, ListNode* head2){ while(head1 != head2){ head1 = head1->next; head2 = head2->next; } return head1; } };
转载于:https://www.cnblogs.com/vercont/p/10210280.html
