[LeetCode] 141 : Linked List Cycle

Naive version

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  bool hasCycle(ListNode *head) {
    std::map<ListNode*, bool> nodeMap;
    ListNode* curNode = head;
    nodeMap[curNode] = true;
    while(curNode != nullptr) {
      curNode = curNode->next;
      if (nodeMap[curNode]) 
        return true;
      else
        nodeMap[curNode] = true;
    }
    return false;
  }
};

Follow up : two pointer version for O(1) memory

/**
 * 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;
  }

  bool hasCycle(ListNode *head) {
    ListNode* stepOneNode = takeOneStep(head);
    ListNode* stepTwoNode = takeTwoStep(head);
    
    while (stepOneNode != nullptr && stepTwoNode != nullptr) {
      if (stepOneNode == stepTwoNode)
        return true;
      stepOneNode = takeOneStep(stepOneNode);
      stepTwoNode = takeTwoStep(stepTwoNode);
    }

    return false;
  }
};