Problem Statement

Given a linked list containing a loop, we aim to determine the starting point of the loop. The starting point is the node where the loop begins.

Examples

Example 1:

Input: list = [1, 2, 3, 4, 5, 6, 10]

Output: tail connects to index 2.

Example 2:

Input: 1->2->3->4->5
          ^        |
          |        |
          +--------+
Output: 2

Explanation: The tailed of the linked list connects to the node at 1st index.

Example 3:

Input: 1->3->7->4->nullptr
Output: nullptr

Explanation: No loop is present in the linked list.

Different Approaches

1️⃣ Brute Force (Hashmap)

We can store nodes in a hash table so that, if a loop exists, the head will encounter the same node again. This node will be present in the table and hence, we can detect the loop.

Algorithm:

1. Iterate the given list.
2. For each node visited by the head pointer, check if the node is present in the hash table.
3. If yes, the loop detected
4. If not, insert the node in the hash table and move the head pointer ahead.
5. If the head reaches null, then the given list does not have a cycle in it.

Code:

#include<bits/stdc++.h>
using namespace std;

class node {
    public:
        int num;
        node* next;
        node(int val) {
            num = val;
            next = NULL;
        }
};

void insertNode(node* &head,int val) {
    node* newNode = new node(val);
    if(head == NULL) {
        head = newNode;
        return;
    }
    node* temp = head;
    while(temp->next != NULL) temp = temp->next;
    
    temp->next = newNode;
    return;
}

void createCycle(node* &head,int pos) {
    node* ptr = head;
    node* temp = head;
    int cnt = 0;
    while(temp->next != NULL) {
        if(cnt != pos) {
            ++cnt;
            ptr = ptr->next;
        } 
        temp = temp->next;
    }
    temp->next = ptr;
}
//process as per mentioned in solution
node* detectCycle(node* head) {
    unordered_set<node*> st;
    while(head != NULL) {
        if(st.find(head) != st.end()) return head;
        st.insert(head);
        head = head->next;
    }
    return NULL;
}

int main() {
    node* head = NULL;
    
    insertNode(head,1);
    insertNode(head,2);
    insertNode(head,3);
    insertNode(head,4);
    insertNode(head,3);
    insertNode(head,6);
    insertNode(head,10);
    
    createCycle(head,2);
    
    node* nodeRecieve = detectCycle(head);
    if(nodeRecieve == NULL) cout<<"No cycle";
    else {
        node* temp = head;
        int pos = 0;
        while(temp!=nodeRecieve) {
            ++pos;
            temp = temp->next;
        }
        cout<<"Tail connects at pos "<<pos<<endl;
    }
    
    return 0;
}

OR:

#include <iostream>
#include <unordered_map>

// Definition of singly linked list
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(NULL) {}
    ListNode(int data1) : val(data1), next(NULL) {}
    ListNode(int data1, ListNode *next1) : val(data1), next(next1) {}
};

class Solution {
public:
    // Function to find the starting point of the loop
    // in a linked list using hashing technique
    ListNode *findStartingPoint(ListNode *head) {
        // Use temp to traverse the linked list
        ListNode* temp = head;

        // hashmap to store all visited nodes
        std::unordered_map<ListNode*, int> mp;

        // Traverse the list using temp
        while(temp != nullptr) {
            // Check if temp has been encountered again
            if(mp.count(temp) != 0) {
                // A loop is detected hence return temp
                return temp;
            }
            // Store temp as visited
            mp[temp] = 1;
            // Move to the next node
            temp = temp->next;
        }

        // If no loop is detected, return nullptr
        return nullptr;
    }
};

// Function to create a linked list with a loop for testing
void createTestList(ListNode* &head, int loop_start_val) {
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    ListNode* node5 = new ListNode(5);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    head = node1;

    // Create a loop from node5 to the specified node
    ListNode* temp = head;
    while (temp != nullptr && temp->val != loop_start_val) {
        temp = temp->next;
    }
    node5->next = temp; // Creating the loop
}

int main() {
    // Create a sample linked list with a loop
    ListNode* head = nullptr;
    createTestList(head, 2); // Creating a loop starting at node with value 2

    // Create an instance of the Solution class
    Solution solution;

    // Detect the starting point of the loop in the linked list
    ListNode* loopStartNode = solution.findStartingPoint(head);

    if (loopStartNode) {
        std::cout << "Loop detected. Starting node of the loop is: " << loopStartNode->val << std::endl;
    } else {
        std::cout << "No loop detected in the linked list." << std::endl;
    }

    // Clean up memory (free the allocated nodes)
    ListNode* temp = head;
    std::unordered_map<ListNode*, bool> visited;
    while (temp != nullptr && visited[temp] == false) {
        visited[temp] = true;
        ListNode* next = temp->next;
        delete temp;
        temp = next;
    }

    return 0;
}

Complexity Analysis

• Time Complexity: O(n)
  • Iterating for the entire list once
• Space Complexity: O(n)
  • We store all nodes in hash table.

2️⃣ Slow and Fast Pointer Approach

Intuition:

• Detecting the Loop:
  • Two Pointer Approach: We use two pointers, slow and fast, both starting at the head of the linked list.
  • Movement of Pointers: The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
  • Meeting Point: If there is a loop in the linked list, these two pointers will eventually meet within the loop. This happens because the fast pointer, moving at double the speed of the slow pointer, will "lap" the slow pointer inside the loop.
  • Finding the Loop's Start: Once a loop is detected, reset the slow pointer to the head of the linked list. Then, move both the fast and slow pointers one step at a time. The point where they meet again is identified as the starting point of the loop. This method ensures efficient detection and pinpointing of the loop's starting location in the linked list.
• Why They Meet:
  • Imagine two runners on a circular track: one running twice as fast as the other. The faster runner will eventually catch up to the slower runner, regardless of where they start. This meeting point within the loop confirms the presence of a cycle.

Visualization:

Consider a linked list with a loop:

A -> B -> C -> D -> E -> F
           ^              |
           |______________|

In this linked list:

• The loop starts at node C.
• The nodes before the loop are A and B.
• The loop is formed by nodes C -> D -> E -> F -> C.

Step-by-Step Breakdown:

1 Initialization:

• slow and fast pointers both start at A (head of the list).

2 Moving Pointers to Detect Loop:

• Move slow by one step and fast by two steps in each iteration:

• Meeting Point: slow and fast meet at node E, confirming a loop exists.

3 Finding the Start of the Loop:

• Reset slow to A (head of the list).
• Move both slow and fast one step at a time:

• Start of the Loop: slow and fast both meet at node C, which is the start of the loop.

Algorithm:

1. Initially take two pointers, fast and slow. The fast pointer takes two steps ahead while the slow pointer will take a single step ahead for each iteration.
2. We know that if a cycle exists, fast and slow pointers will collide.
3. If the cycle does not exist, the fast pointer will move to NULL.
4. Else, when both slow and fast pointer collides, it detects a cycle exists.
5. Take another pointer, say entry. Point to the very first of the linked list.
6. Move the slow and the entry pointer ahead by single steps until they collide. 
7. Once they collide we get the starting node of the linked list.

Dry Run:

Initial State:

A (Head) -> B -> C -> D -> E -> F -> G
                      ^              |
                      |______________|
Slow = A, Fast = A

1 After 1st Move:

A -> B (slow) -> C (fast) -> D -> E -> F -> G
                      ^                     |
                      |_____________________|

2 After 2nd Move:

A -> B -> C (slow) -> D -> E (fast) -> F -> G
                      ^                     |
                      |_____________________|

3 After 3rd Move:

A -> B -> C -> D (slow) -> E -> F -> G
 (fast)
               ^                     |
               |_____________________|

4 After 4th Move (Got the Loop):

A -> B -> C -> D -> E (slow | fast) -> F -> G
               ^                            |
               |____________________________|

5 Reinitialize the slow to head:

A (slow) -> B -> C -> D -> E (fast) -> F -> G
                      ^                     |
                      |_____________________|

6 Move the slow and fast by one (First Move):

A -> B (slow) -> C -> D -> E -> F (fast) -> G
                      ^                     |
                      |_____________________|

7 Second Move:

A -> B -> C (slow) -> D -> E -> F -> G (fast)
                      ^              |
                      |______________|

8 Third Move:

A -> B -> C -> D (slow | fast) -> E -> F -> G
               ^                            |
               |____________________________|

Return D

Code:

#include <iostream>

using namespace std;
//Definition of singly linked list:
struct ListNode
{
    int val;
    ListNode *next;
    ListNode()
    {
        val = 0;
        next = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};





class Solution {
public:
//Function to find the first node
//Of the loop in a linked list
    ListNode* findStartingPoint(ListNode* head) {
        //Initialize a slow and fast 
        //Pointers to the head of the list
        ListNode* slow = head;
        ListNode* fast = head;

        // Phase 1: Detect the loop
        while (fast != NULL && fast->next != NULL) {
            
            // Move slow one step
            slow = slow->next;
            
            // Move fast two steps
            fast = fast->next->next;

            // If slow and fast meet,
            // a loop is detected
            if (slow == fast) {
                
                // Reset the slow pointer
                // To the head of the list
                slow = head;

                // Phase 2: Find the first node of the loop
                while (slow != fast) {
                    
                    // Move slow and fast one step
                    // At a time
                    slow = slow->next;
                    fast = fast->next;

                    // When slow and fast meet again,
                    // It's the first node of the loop
                }
                
                // Return the first node of the loop
                return slow;
            }
        }
        
        //If no loop is found, 
        //Return NULL
        return NULL;
    }
};

int main() {
    // Create a sample linked list with a loop
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    node1->next = node2;
    ListNode* node3 = new ListNode(3);
    node2->next = node3;
    ListNode* node4 = new ListNode(4);
    node3->next = node4;
    ListNode* node5 = new ListNode(5);
    node4->next = node5;

    // Make a loop from node5 to node2
    node5->next = node2;

    // Set the head of the linked list
    ListNode* head = node1;

    // Detect the loop in the linked list
    Solution sol;
    ListNode* loopStartNode = sol.findStartingPoint(head);

    if (loopStartNode) {
        cout << "Loop detected. Starting node of the loop is: " << loopStartNode->val << endl;
    } else {
        cout << "No loop detected in the linked list." << endl;
    }

    // Clean up memory (free the allocated nodes)
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
  • The code examines each node in the linked list exactly once, where n is the total number of nodes. This results in a linear time complexity, O(n).
• Space Complexity: O(1)
  • The code uses a fixed amount of extra space, regardless of the size of the linked list.