LeetCode Linked List Cycle: Two Pointers, Reversal and Hash

Overview

LeetCode Linked List Cycle could be solved by slow/fast pointers and reversing the linked list or by using hashing method. I compare these three methods here.

LeetCode Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Two (slow/fast) Pointers Solution

By similar idea to find the middle node of a linked list, we maintain two pointers, the slow pointer to scan the linked list one step by one step and the fast pointer to scan the linked list two steps at time. If there is a cycle, the fast pointer will overlap the slow pointer sometime, if there is no cycle, the scanning could be ended normally once reaching to the end of the linked list. To detect such overlapping, we need the maintain the complete information about the nodes the fast pointer went through, so we keep two separate pointers for the faster scanning and if there is a cycle, the slow pointer must be overlapped with one of these two fast pointers (think about the details of the reason here). And the following code is accepted by LeetCode OJ to pass this Linked List Cycle problem:

bool hasCycle(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast1 = head;
    ListNode *fast2 = head;
    while (slow && (fast1 = fast2->next) && (fast2 = fast1->next) ) {
        if (slow == fast1 || slow == fast2) return true;
        slow = slow->next;
    }
    return false;
}

Update: the following one might be less elegant but is useful for the follow up question to return the start node of the cycle, and the only difficulty for me to see about this algorithm is that I found it difficult to prove that the following slow/fast pointer meets at the same node in O(N) time, how and what key fact guarantee that they could meet at the same time in O(N) bound? Anyone could point me to some reference and that would highly appreciated!

bool hasCycle(ListNode *head) {
    if (NULL == head) return NULL;
    ListNode *slow = head;
    ListNode *fast = head->next;

    while (slow && fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Reverse the Linked List Solution

Well, if we are allowed to change the structure of the input linked list, there is another solution by reversing the linked list (refer the to standard reverse linked list problem for further information: “LeetCode Reverse Linked List II: One Pass“). The key fact here is that, if there is a cycle, when we progress to reverse the linked list, at some time point, we would return to the init head node, so by keeping the original head node and compare it with the current node we are trying to reverse, we can decide if there is a cycle. The time complexity is still O(N), think about why. And the following is the code accepted by LeetCode OJ to pass this Linked List Cycle problem:

bool hasCycle(ListNode *head) {
    if (NULL == head) return false;
    ListNode *init = head;

    ListNode *prev = NULL;
    ListNode *curr = head;
    ListNode *next = head->next;
    curr->next = NULL;
    while (curr && next) {
        prev = curr, curr = next, next = next->next;
        if (curr == init) return true;
        curr->next = prev;
    }
    return false;
}

Hash Approach

Well another alternative approach to solve this linked list cycle problem is by using hashing, we scan the linked list from the head and for each node of the linked list, we use a hash map to keep a counting of the visited times, if we got any node that has more than one visit time, then there is a cycle. This approach is trivial.

Summary

I discussed three methods: slow/fast pointers, reversing the linked list, by using hashing method to solve this LeetCode Linked List Cycle problem. You are very welcome to share your comments!

Written on December 8, 2014