leetcode142-cycle-list-2_fast_slow_pointer_solution.cpp

#include<iostream>
#include<vector>
#include<algorithm>
usingnamespacestd;

/**
 * Definition for singly-linked list.
*/
structListNode {
int val;
 ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

classSolution {
public:
 ListNode *detectCycle(ListNode *head) {
 ListNode* slow = head;
 ListNode* fast = head;

while (fast != NULL && fast->next != NULL)
 {
 slow = slow->next;
 fast = fast->next->next;
if (slow == fast)
break;
 }
/* 处理上一轮遍历结束时的临界情况 */
if (fast == NULL || fast->next == NULL)
returnNULL;
 slow = head;
while (fast != slow) /* 只要还没相遇就继续循环 */
 {
 slow = slow->next;
 fast = fast->next; /* 此轮循环每次只走一步 */
 }
return slow;
 }
};

// Test
intmain()
{
 Solution sol;
 ListNode *n1 = newListNode(3);
 ListNode *n2 = newListNode(2);
 ListNode *n3 = newListNode(0);
 ListNode *n4 = newListNode(-4);
 n1->next = n2;
 n2->next = n1;
 n2->next = n3;
 n3->next = n4;
 n4->next = n2; 

 ListNode* meet = sol.detectCycle(n1);
 cout << meet->val << endl;

return0;
}