You signed up for an escape room experience, but something feels off.
The facility has $N$ rooms, numbered $1$ through $N$. Each room has a single door that leads to exactly one other room — or directly outside. You start from room $1$ and follow the doors one by one.
Twenty minutes in, your partner grabs your arm. "We've walked through this room before."
She's right. Somewhere in the layout, an exit circles back. If that loop exists, you're going to keep walking the same stretch of hallway forever. The first room you step into for the second time is where the loop begins.
Given the exit map, find that room. If the path eventually leads outside, output the number of the last room you pass through before the exit.
Implement the following function:
Node *detectCycle(Node *head);
The Node struct is defined in function.h:
typedef struct Node { struct Node *next; } Node;
head points to room $1$. Return the node where the loop begins, or the last node before the exit if no loop exists.
Hint: Compare pointers directly — do not attempt to store or index nodes by values of any kind. Any solution that allocates auxiliary storage proportional to $N$ will exceed the memory limit on the large test cases.
The first line contains an integer $N$.
The following $N$ lines: the $i$-th line contains a single integer $\text{nxt}[i]$ — the room that room $i$'s door leads to. $\text{nxt}[i] = 0$ means the door exits the facility.
If a loop exists, output the room number where it begins (the first room visited twice).
If no loop exists, output the number of the last room visited before the exit.