Reversing a list (iterative and recursive); finding the middle; detecting a cycle (fast/slow pointers)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• To insert n after p, which pointer is set first? from Lesson 3.4.1
• In a circular queue of size N, how many items does (rear − front + N) % N give? from Lesson 3.3.2
• Why does a function that changes the caller’s pointer need a pointer to a pointer? from Lesson 1.4.2

1 · The Hook

🎣

Reversing a train means turning every coupling around, not moving the coaches. Finding the middle coach of a train whose length you do not know: send two walkers from the engine, one taking one coach per step and the other two; when the fast one reaches the end, the slow one is in the middle. The same two-speed trick detects a track that loops back on itself.

2 · Predict First

🤔

What does this print?

struct node *reverse(struct node *head)
{
    struct node *prev = NULL, *cur = head, *nxt;
    while (cur != NULL) {
        nxt = cur->next;     /* remember the rest */
        cur->next = prev;    /* turn the arrow around */
        prev = cur;          /* step forward */
        cur = nxt;
    }
    return prev;             /* new head */
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5};
    struct node *head = reverse(build(a, 5));
    printList(head);
    return 0;
}

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Output

5 4 3 2 1

Each node’s next is turned to point to the node before it; the old last node becomes the new head.

Iterative reverse: three pointers

Walk with prev (already reversed part), cur (node being turned) and nxt (saved rest). Each step: save nxt = cur->next, turn cur->next = prev, advance prev = cur, cur = nxt. At the end prev is the new head. O(n) time, O(1) extra space.

Recursive reverse

Reverse everything after the head, then make the old second node point back to the head, and cut the head’s own next. O(n) time, O(n) stack depth.

struct node *rrev(struct node *head)
{
    struct node *rest;
    if (head == NULL || head->next == NULL)
        return head;
    rest = rrev(head->next);     /* reverse everything after head */
    head->next->next = head;     /* the old second node now points back */
    head->next = NULL;
    return rest;
}

int main(void)
{
    int a[] = {10, 20, 30, 40};
    printList(rrev(build(a, 4)));
    return 0;
}

Output

40 30 20 10

Middle with slow and fast pointers

Move slow one node and fast two nodes per step, while fast and fast->next exist. When fast stops, slow is at the middle: for 7 nodes the 4th; for an even count (6) this version stops at the second of the two middle nodes (the 4th).

int middle(struct node *head)
{
    struct node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;           /* one step */
        fast = fast->next->next;     /* two steps */
    }
    return slow->data;
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6, 7};
    printf("%d %d\n", middle(build(a, 7)), middle(build(a, 6)));
    return 0;
}

Output

4 4

Detecting a cycle (Floyd)

If a list loops back on itself (some node’s next points to an earlier node), a traversal never reaches NULL. With slow (1 step) and fast (2 steps), fast either reaches NULL (no cycle) or, inside the loop, gains one node per step on slow and must land on it: slow == fast means a cycle. O(n) time, O(1) space — no need to mark visited nodes.

int hasCycle(struct node *head)
{
    struct node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return 1;
    }
    return 0;
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6};
    struct node *h1 = build(a, 6), *h2 = build(a, 6), *p = h2, *third;
    while (p->next != NULL) p = p->next;      /* p = last node (6) */
    third = h2->next->next;                   /* node 3 */
    p->next = third;                          /* 6 -> 3 makes a loop */
    printf("%d %d\n", hasCycle(h1), hasCycle(h2));
    return 0;
}

Output

0 1

4 · Visual

Iterative reverse of 1 -> 2 -> 3 -> NULL

          prev        cur         nxt        list state
start     NULL        1           -          1->2->3->NULL
step 1    1           2           2          NULL<-1   2->3->NULL
step 2    2           3           3          NULL<-1<-2   3->NULL
step 3    3           NULL        NULL       NULL<-1<-2<-3     -> return prev (3)

Floyd on 1 2 3 4 5 6 with 6 -> 3 (loop 3 4 5 6):
step   slow   fast
 0      1      1
 1      2      3
 2      3      5
 3      4      3      (5 -> 6 -> 3)
 4      5      5      meet: cycle found

Three pointers turn the arrows one by one; two speeds meet inside a loop.

The second list of the program: node 6’s next points back to node 3 (drawn as the missing arrow after 6). slow and fast meet at node 5 after 4 steps.

5 · Worked Examples

Example 1 Easy

What does this print?

int middle(struct node *head)
{
    struct node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;           /* one step */
        fast = fast->next->next;     /* two steps */
    }
    return slow->data;
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6, 7};
    printf("%d %d\n", middle(build(a, 7)), middle(build(a, 6)));
    return 0;
}

Solution

7 nodes: slow visits 2, 3, 4 while fast visits 3, 5, 7; fast->next is NULL, stop: 4. 6 nodes: slow 2, 3, 4; fast 3, 5, then NULL: 4 (the second middle).

Output

4 4

Example 2 Medium

Trace the iterative reverse of 1 → 2 → 3. How many next pointers are changed?

Solution

See the table: each node’s next is changed exactly once: 3 changes for 3 nodes (n for n nodes).

Example 3 GATE

What does this print, and after how many steps do slow and fast meet in the looped list?

int hasCycle(struct node *head)
{
    struct node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return 1;
    }
    return 0;
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6};
    struct node *h1 = build(a, 6), *h2 = build(a, 6), *p = h2, *third;
    while (p->next != NULL) p = p->next;      /* p = last node (6) */
    third = h2->next->next;                   /* node 3 */
    p->next = third;                          /* 6 -> 3 makes a loop */
    printf("%d %d\n", hasCycle(h1), hasCycle(h2));
    return 0;
}

Solution

The first list ends in NULL: 0. In the second, 6 → 3 forms a loop of 4 nodes; tracing gives a meeting after 4 steps at node 5: 1.

Output

0 1

6 · GATE Traps

⚠️

• In iterative reverse, save cur->next before overwriting it.
• The new head is prev, not cur (cur is NULL at the end).
• Recursive reverse must set head->next = NULL, or a 2-node loop remains.
• For an even number of nodes, check which middle a given loop condition returns.
• Cycle detection must check fast != NULL && fast->next != NULL before stepping.

8 · Memory Hook

🧠

“Save, turn, step.” For reversing; and “the hare laps the tortoise only on a circular track” for cycles.

9 · Connect the Dots

Lessons 3.4.1–3.4.2 used nodes with a single next pointer, so moving backwards or deleting a node without its predecessor was impossible. Next lesson answers: what do we gain by giving each node a pointer to its previous node too, or by joining the last node back to the first?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ2 marksOutput

What does this print?

struct node *rrev(struct node *head)
{
    struct node *rest;
    if (head == NULL || head->next == NULL)
        return head;
    rest = rrev(head->next);     /* reverse everything after head */
    head->next->next = head;     /* the old second node now points back */
    head->next = NULL;
    return rest;
}

int main(void)
{
    int a[] = {10, 20, 30, 40};
    printList(rrev(build(a, 4)));
    return 0;
}

• (A) 40
• (B) 10
• (C) 10 20 30 40
• (D) 40 30 20 10

Q2MCQ1 markMiddle

With slow/fast pointers (loop while fast and fast->next exist), which node does slow end on for a 10-node list (1-based)?

• (A) 6
• (B) 5
• (C) 4
• (D) 10

Q3MCQ1 markCycle

Floyd’s cycle detection uses:

• (A) O(n) extra space
• (B) O(1) extra space
• (C) recursion
• (D) sorting

Q4NAT1 markReverse

How many next pointers does iterative reverse change in a list of 8 nodes?

Numerical answer: ________

Q5MSQ2 marksFacts

Which are true?

• (A) A list with a cycle has a node whose next is NULL.
• (B) If fast ever equals slow (after moving), the list has a cycle.
• (C) Iterative reversal needs O(1) extra space.
• (D) Recursive reversal uses O(n) stack space.

11 · Rule Card

• Reverse: while (cur) { nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } return prev;
• Recursive: rest = rrev(head->next); head->next->next = head; head->next = NULL;
• Middle: slow +1, fast +2 while fast && fast->next; even n → second middle.
• Cycle: slow == fast ⇒ cycle; fast hits NULL ⇒ none. O(n) time, O(1) space.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

reverse a listprev / cur / next pointersslow and fast pointerscycle (loop) in a listFloyd cycle detection

13 · Answer Vault