[LeetCode 141] 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?

Diffculty
Easy

Similar Problems

Analysis

Floyd’s Cycle-Finding Algorithm: This is the fastest method. Traverse linked list using two pointers.
Move one pointer by one and other pointer by two.
If these pointers meet at some node then there is a loop.
If pointers do not meet then linked list doesn’t have loop.

class Solution { public: bool hasCycle(ListNode head) { if(head == NULL) return false; ListNode slow = head; ListNode *fast = head->next;

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

};

void detectAndRemoveLoop(Node head){ Node slow = head; Node *fast = head->next;

// Search for loop using slow and fast pointers
while (fast && fast->next){
    if (slow == fast)
        break;
    slow = slow->next;
    fast = fast->next->next;
}

/* If loop exists */
if (slow == fast){
    slow = head;
    while (slow != fast->next){
        slow = slow->next;
        fast = fast->next;
    }

    /* since fast->next is the looping point */
    fast->next = NULL; /* remove loop */
}

}