Linked List Cycle Solutions in C++

// Source : https://oj.leetcode.com/problems/linked-list-cycle/
// Author : Hao Chen
// Date   : 2014-07-03




/**
 * 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) {
        return hasCycle04(head);
        return hasCycle03(head);
        return hasCycle02(head);
        return hasCycle01(head);
    }


    // using a map to store the nodes we walked
    bool hasCycle01(ListNode *head) {
        unordered_map<ListNode*,bool > m;
        ListNode* p = head;
        m[(ListNode*)NULL] = true;
        while( m.find(p) == m.end() ) {
            m[p] = true;
            p = p -> next;
        }
        return p != NULL;
    }

    // Change the node's of value, mark the footprint by a special value
    bool hasCycle02(ListNode *head) {
        ListNode* p = head;
        // using INT_MAX as the mark could be a bug!
        while( p &&  p->val != INT_MAX ) {
            p->val = INT_MAX;
            p = p -> next;
        }
        return p != NULL;
    }

    /*
     * if there is a cycle in the list, then we can use two pointers travers the list.
     * one pointer traverse one step each time, another one traverse two steps each time.
     * so, those two pointers meet together, that means there must be a cycle inside the list.
     */
    bool hasCycle03(ListNode *head) {
        if (head==NULL || head->next==NULL) return false;
        ListNode* fast=head;
        ListNode* slow=head;
        do{
            slow = slow->next;
            fast = fast->next->next;
        }while(fast != NULL && fast->next != NULL && fast != slow);
        return fast == slow? true : false;
    }

    // broken all of nodes 
    bool hasCycle04(ListNode *head) {
         ListNode dummy (0);
        ListNode* p = NULL;

        while (head != NULL) {
            p = head;
            head = head->next;

            // Meet the old Node that next pointed to dummy
            //This is cycle of linked list
            if (p->next == &dummy) return true;

            p->next = &dummy; // next point to dummy
        }
        return false;
    }

};

/// Source : https://leetcode.com/problems/linked-list-cycle/description/
/// Author : liuyubobobo
/// Time   : 2017-11-02

#include <iostream>
#include <unordered_set>

using namespace std;

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


/// Using Hash Table
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    bool hasCycle(ListNode *head) {

        if(head == NULL)
            return false;

        // Use long long type for 64-bit os
        unordered_set<long long> node_address;

        ListNode* p = head;
        while(p != NULL){
            if(node_address.find((long long)(p)) == node_address.end())
                node_address.insert((long long)(p));
            else
                return true;

            p = p->next;
        }

        return false;
    }
};

int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/linked-list-cycle/description/
/// Author : liuyubobobo
/// Time   : 2017-11-02

#include <iostream>
#include <unordered_set>

using namespace std;

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


/// Two Pointers - fast and slow
/// faster pointer moves two steps a time, and slow pointer moves one step a time.
///
/// faster pointer will meet slow pointer eventually.
/// Simple prove: suppose faster pointer is x steps behind slow pointer
/// if x == 1, then in the next time, fast pointer will meet slow pointer
/// if x > 1, then in the next tme, fast pointer will get one step closer to slow pointer
///           the process continues until faster pointer is just one step behind slow pointer
///           thenm in the next time, they meet together:)
///
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    bool hasCycle(ListNode *head) {

        if(head == NULL)
            return false;

        if(head->next == NULL)
            return false;

        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast != slow){
            if(fast->next == NULL)
                return false;
            if(fast->next->next == NULL)
                return false;

            fast = fast->next->next;
            slow = slow->next;
        }

        return true;
    }
};

int main() {

    return 0;
}