2.6 Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.

2.6.cpp

#include<iostream>

using namespace std;

struct Node
{
    int data;
    Node *next;
    
    Node(int data, Node *next) {
        this->data = data;
        this->next = next;
    }
    
    ~Node() {}
};

typedef Node* pNode;

pNode isCircular(pNode head)
{
    pNode fast(head), slow(head);
    
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) break;
    }
    
    if (fast == nullptr || fast->next == nullptr) return nullptr;
    
    for (slow = head; slow != fast; slow = slow->next, fast = fast->next);
    
    return slow;
}

void print(Node * head)
{
    pNode loop = isCircular(head);
    bool isLoopPrinted(false);
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
        if (head == loop) {
            if (isLoopPrinted) {
                cout << head->data << "* ";
                break;
            } else
                isLoopPrinted = true;
        }
    }
    cout << endl;
}

void clear(Node *head)
{
    if (head != nullptr) {
        pNode loop = isCircular(head);
        bool isLoopDeleted(false);
        while(head->next != loop && isLoopDeleted) {
            Node *t = head->next;
            head->next = t->next;
            delete t;
            if (t == loop) isLoopDeleted = true;
        }
        delete head;
    }
}

int main(int argc, char *argv[])
{
    Node *loop = new Node(2, nullptr);
    Node *a = new Node(7, loop);
    loop->next = new Node(1, new Node(6, loop));
    print(a);
    clear(a);
    return 0;
}