[LeetCode] 142 Linked List Cycle II

 延續LeetCode 141

先用快慢指針找到相遇點

再從head跟相遇點用一樣速度前進, 就會遇到cycle的進入點

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* takeOneStep(ListNode *node) {
    if (node == nullptr)
      return nullptr;
    return node->next;
  }
  ListNode* takeTwoStep(ListNode *node) {
    if (node == nullptr)
      return nullptr;
    ListNode* tmp = node->next;
    if (tmp == nullptr)
      return nullptr;
    return tmp->next;
  }
  // LeetCode 141. Linked List Cycle
  ListNode *foundMeetingPoint(ListNode *head) {
    ListNode* stepOneNode = takeOneStep(head);
    ListNode* stepTwoNode = takeTwoStep(head);
    
    while (stepOneNode != nullptr && stepTwoNode != nullptr) {
      if (stepOneNode == stepTwoNode)
        break;
      stepOneNode = takeOneStep(stepOneNode);
      stepTwoNode = takeTwoStep(stepTwoNode);
    }
    if (stepOneNode == nullptr || stepTwoNode == nullptr)
      return nullptr;
    return stepOneNode;
  }
  ListNode *detectCycle(ListNode *head) {
    // Step 1 : find meeting point in cycle
    ListNode *meet = foundMeetingPoint(head);
    if (meet == nullptr)
      return nullptr;
    // Step 2 : the middle point of head and meeting point is entry point of cycle
    ListNode *start = head;
    while(meet != start) {
      start = takeOneStep(start);
      meet = takeOneStep(meet);
    }
    return start;
  }
};