Problem
Given a linked list, return the node where the cycle begins. If there is no cycle, return
null
.
Follow up:
Can you solve it without using extra space?
Can you solve it without using extra space?
Code
ListNode *detectCycle(ListNode *head) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. ListNode *p1 = head; if(!p1) return 0; ListNode *p2 = p1; while(p1 && p2){ p1 = p1->next; p2 = p2->next; if(p2) p2 = p2->next; if(p1 && p1 == p2) break; } if(p2 && p1){ ListNode *p3 = head; while(p1 != p3){ p1 = p1->next; p3 = p3->next; } return p3; } return 0; }
No comments:
Post a Comment