Find start of loop in linked list

Find the start of a loop in a linked list (if it exists).  Only the head of the linked list is provided.
/*
 * StartOfLoop.cpp
 *
 *  Created on: Apr 18, 2012
 *      Author: Kiran Hegde
 */

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

struct Node {
    int data;
    Node *next;
};

/**
 * Generate a linked list of size containing random numbers from 0 to 9
 */
Node *createCircularLinkedList(int totalSize, int loopSize) {
    srand(time(NULL));
    Node *head = NULL;
    Node *last = NULL;
    for (int i = 0; i < totalSize; i++) {
        Node *node = new Node;
        node->data = rand() % totalSize; //random numbers from 0 to totalSize-1
        node->next = head;
        head = node;
        if (i == 0) {
            last = node;
        }
    }
    // get node that is loopSize from end
    if (loopSize > 0) {
        Node *p = head;
        int count = 0;
        while (count < totalSize - loopSize) {
            p = p->next;
            count ++;
        }
        //point the last node to the above node to create the loop
        last->next = p;
    }
    return head;
}

void deleteCircularLinkedList(Node *head, int size) {
    int count = 0;
    while ((head != NULL) && (count < size)) {
        Node *temp = head;
        head = head->next;
        delete temp;
        count++;
    }
}

void printCircularLinkedList(Node *head, int totalSize, int loopSize) {
    Node *curr = head;
    int count = 0;
    while ((curr != NULL) && (count <= totalSize)) {
        cout << curr->data;
        curr = curr->next;
        if ((count == totalSize) || (count == (totalSize - loopSize)))
            cout << "*";
        if (count < totalSize)
            cout << "-->" ;
        count++;
    }
    if (curr == NULL)
        cout << "EMPTY" << endl;
    else
        cout << endl;
}

/**
 * Return true if there is a circular loop in a linked list
 */
bool containsLoop(Node *head) {
    Node *slow = head;
    Node *fast = head;
    bool isLoop = false;
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast) {
            isLoop = true;
            break;
        }
    }
    return isLoop;
}
/**
 * This is a popular solution based on creating fast and slow runners that
 * traverse the linked list.  fast runner traverses twice as fast as slow.
 * If head is "N" nodes before the start of the loop, by the time slow
 * runner reaches the start of loop, fast runner would have traversed
 * N nodes into the loop.  Basically, the fast runner would be (loopSize - N)
 * behind slow runner at this point.  When the two meet, they will be N
 * nodes before the start of the loop.  After the two meet, move one of
 * the runners back to the head.  Now, traverse till the two meet again.
 * This will give us the beginning of loop.
 */
Node *findStartOfLoop(Node *head) {
    Node *slow = head;
    Node *fast = head;
    bool isLoop = false;
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast) {
            isLoop = true;
            break;
        }
    }
    if (!isLoop)
        return NULL;
    //Move fast pointer to head
    fast = head;
    //Move both pointers one step at a time till they meet
    while (fast != slow) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

/**
 * Test the code
 */
int main() {
    Node *head = createCircularLinkedList(50, 10);
    cout << "The List: ";
    printCircularLinkedList(head, 50, 10);
    bool loop = containsLoop(head);
    cout << "Linked List Contains Loop: " <<
            (loop ? "Yes" : "No") << endl;
    if (loop) {
        Node *node = findStartOfLoop(head);
        cout << "The loop is at Node with value: " << node->data << endl;
    }
    deleteCircularLinkedList(head, 50);
    return 0;
}
Comments