[LeetCode] Linked List Cycle I & II

Linked List Cycle I

Problem Statement (link here):

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

Analysis:

A straightforward solution is to store each visited node in a vector as we traverse the linked list, and each time we encounter a new node, we compare the node with existing nodes in vector, if we found a match, it implies the list has a cycle; if we move to a NULL node and no match found, it implies the list doesn't have a cycle. This algorithm requires O(n) space and O(n^2) time complexity - searching and comparing.

The problem statement doesn't allow extra space, we need to find another solution. A classic two-pointer technique would work for this problem.

We define a slow pointer and a fast pointer. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If there's a cycle, the two pointer will meet again, mathematically; if there's no cycle, the fast pointer will hit NULL before the slow pointer. This algorithm is O(n) in time complexity, and doesn't use any extra space - except for two pointers - O(1).

Code:

/**
 * 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) {
        if (head==NULL || head->next==NULL) return false;
        ListNode *slow = head;
        ListNode *fast = head->next;
       
        while (fast != NULL){
            if (fast == slow)
                return true;
            else if (fast->next == NULL)
                return false;
            else {
                slow = slow->next;
                fast = fast->next->next;
            }
        }
        return false;
    }
};

Take-aways:
Two pointer technique is useful for detecting cycles in a data structure.

Linked List Cycle II

Problem Statement (link here):

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?

Analysis:

Let's look at an example below:

                                         a --> b --> c --> d --> e --> f --> g
                                                                             |               |
                                                                             j <--  i <-- h

Imagine if we know the number of nodes in the cycle - 6 in the above example, we could use two pointers to find node e: one pointer  points starts at node a, the other pointer starts at 6 nodes away - node g. A bit math shows that if the two pointers moves at the same pace, they would eventually meet at node e, which is exactly the start of the cycle.

Okay, then how could we find the number of nodes in the cycle? Aha, we could use what we learned from Linked List Cycle I, as the two pointers will meet on some node in the cycle, if we fix that meeting node, and do a traverse, we could count the number of nodes it traversed, which is the number of nodes in the cycle.

Obviously, if there's no cycle, the Linked List Cycle I algorithm will tell us so and we could return the function right away.

As we are doing some simple traverses, the time complexity would be linear: O(n), where n is number of nodes in the list.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head==NULL || head->next==NULL) return NULL;
        // determine if there's a loop
        int num=1;  // number of nodes in cycle
        bool hasCycle=false;
        ListNode *slow=head;
        ListNode *fast=head->next;

        while(fast!=NULL) {
            if (slow==fast) { hasCycle=true; break;}
            else if (fast->next==NULL) return NULL;
            else {
                slow=slow->next; fast=fast->next->next;
            }
        }
        if (!hasCycle) return NULL;
        // find number of nodes - k - in a loop
        // - fix one ptr in cycle, move the other ptr until meet
        fast=fast->next;
        while(slow!=fast) {
            fast=fast->next;
            num++;
        }
        // two pointers moves in same pace, one starts at head, other starts at k node away
        // when they meet, the node is where cycle begins
        slow=fast=head;
        while(num>0) {
            fast=fast->next;
            num--;
        }

        while(slow!=fast) {
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};