linked list cycle I and II

linked list cycle I and II

These two question I have never met before, and looks interesting.

Linked list I

A fast pointer and a slow pointer,each time the fast one walk two steps and the slow one walk one step. If there is a cycle and the the fast one will meet the slow one one.

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     bool hasCycle(ListNode *head) {
12         if ( !head ) {
13             return false;
14         }
15         ListNode* fast = head;
16         ListNode* slow = head;
17         while ( fast->next && fast->next->next ) {
18             slow = slow->next;
19             fast = fast->next->next;
20             if ( fast == slow ) {
21                 return true;
22             }
23         }
24         return false;
25     }
26 };

Linked list cycle II

This seems a little harder than Linked list cycleI. Assuming that, the lenth of the cycle is len, and when the two pointer meet, the slow one walked m steps, and there are b steps between the enterance of the cycle and the point where they meet.

  1. When the two pointer meet, the slow one walked m steps, and the fast one walked 2m steps.
  2. So 2m - m = k*len means the fast one walked serveral cycles.
  3. The entrance to of the cycle is at m-b
  4. Now ,apparently, the head to the enterance and the meet point to the enterance are both m-b.
  5. Make the slow pointer back to the head, the fast pointer stay at where they meet. This time, both of them walk one step each iteration. Finally they will meet in the enterance.
 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *detectCycle(ListNode *head) {
12         if ( !head ) {
13             return head;
14         }
15         ListNode* fast = head;
16         ListNode* slow = head;
17         int mark = 0;
18         while ( fast->next && fast->next->next ) {
19             slow = slow->next;
20             fast = fast->next->next;
21             if ( fast == slow ) {
22                 mark = 1;
23                 break;
24             }
25         }
26         if ( 0 == mark ) {
27             return NULL;
28         }
29         slow = head;
30         while ( fast != slow ) {
31             fast = fast->next;
32             slow = slow->next;
33         }
34         return fast;
35     }
36 };

Loading Disqus comments...
Table of Contents