Find start node of the cycle in a linked list
Given a linked list containing a cycle, return the starting node of the cycle without modifying the list. Report if there are no cycles in the linked list.
For instance, the linked list below has a cycle, and the cycle begins at node 2.
We can easily identify if the linked list contains a cycle or not using Floyd’s cycle detection algorithm. The idea is to take two pointers, slow and fast, where the fast pointer moves through the list at double the speed as the slow pointer. The cycle is present in the list if both pointers cross at any node in the linked list. In order to locate the start of the cycle in the linked list, we can take another pointer that begins at the head node and move it along with the slow pointer (from its last location) at a normal pace. The cycle in the linked list begins at the position where this pointer and the slow pointer intersect.
Following is the C++, Java, and Python implementation based on the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <iostream> #include <vector> using namespace std; // A Linked List Node struct Node { int data; Node* next; Node(int data, Node* next) { this->data = data; this->next = next; } }; Node* detectCycle(Node *head) { // base case if (!head || !head->next) { return nullptr; } // take two pointers – `slow` and `fast` Node *slow = head, *fast = head; while (fast->next && fast->next->next) { // move `slow` by one pointer slow = slow->next; // move `fast` by two pointers fast = fast->next->next; // if `slow` and `fast` pointers meet at any node, the linked list contains a cycle if (slow == fast) { // find the start node of the cycle Node *start = head; while (slow != start) { slow = slow->next; start = start->next; } return start; } } // we reach here if the linked list does not contain a cycle return nullptr; } int main() { vector<int> keys = { 1, 2, 3, 4 }; // construct linked list from keys Node* head = nullptr; for (int i = keys.size() - 1; i >= 0; i--) { head = new Node(keys[i], head); } // insert cycle from node 4 to node 2 head->next->next->next->next = head->next; Node* start = detectCycle(head); if (start) { cout << "Cycle found starting from node " << start->data; } else { cout << "Linked list doesn't contain any cycle"; } return 0; } |
Output:
Cycle found starting from node 2
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } } public class Main { public static Node detectCycle(Node head) { // base case if (head == null || head.next == null) { return null; } // take two pointers – `slow` and `fast` Node slow = head, fast = head; while (fast.next != null && fast.next.next != null) { // move `slow` by one pointer slow = slow.next; // move `fast` by two pointers fast = fast.next.next; // if `slow` and `fast` pointers meet at any node, // the linked list contains a cycle if (slow == fast) { // find the start node of the cycle Node start = head; while (slow != start) { slow = slow.next; start = start.next; } return start; } } // we reach here if the linked list does not contain a cycle return null; } public static void main(String[] args) { int[] keys = { 1, 2, 3, 4 }; // construct linked list from keys Node head = null; for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); } // insert cycle from node 4 to node 2 head.next.next.next.next = head.next; Node start = detectCycle(head); if (start != null) { System.out.println("Cycle found starting from node " + start.data); } else { System.out.println("Linked list doesn''t contain any cycle"); } } } |
Output:
Cycle found starting from node 2
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next def detectCycle(head): # base case if head is None or head.next is None: return None # take two pointers – `slow` and `fast` slow = fast = head while fast.next and fast.next.next: # move `slow` by one pointer slow = slow.next # move `fast` by two pointers fast = fast.next.next # if `slow` and `fast` pointers meet at any node, the linked list contains a cycle if slow == fast: # find the start node of the cycle start = head while slow != start: slow = slow.next start = start.next return start # we reach here if the linked list does not contain a cycle return None if __name__ == '__main__': keys = [1, 2, 3, 4] # construct linked list from keys head = None for i in reversed(range(len(keys))): head = Node(keys[i], head) # insert cycle from node 4 to node 2 head.next.next.next.next = head.next start = detectCycle(head) if start: print('Cycle found starting from node', start.data) else: print('Linked list doesn\'t contain any cycle') |
Output:
Cycle found starting from node 2
The time complexity of the above solution is O(n) and works in O(1) space, where n is the total number of nodes in the linked list.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)