SyntaxPilot
Courses/C Coding Questions/Lesson 27
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C Coding Questions · Lesson 27 of 30

Linked list questions II

reverse a linked listfind the middle (slow/fast pointers)detect a loop (Floyd's cycle detection)

These are the notes for C Coding Questions, episode 27, placement practice for people who finished the SyntaxPilot C course. Linked list questions, part two, three of the most asked interview questions: reversing a linked list in place, finding the middle node in one pass with slow and fast pointers, and detecting a loop with Floyd's cycle detection (the tortoise and the hare).

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, glibc, Linux x86-64), the SyntaxPilot compiler's C command with warnings on, and every output below is real. The fixed programs were also run under valgrind --leak-check=full: no errors and no leaks. The node type, print_list and free_list are the ones from episode 26; to keep the question's code on top, each program declares its helpers first and defines them at the bottom.

Real-life pictures

In real life In C
re-hooking every coach of a train to face the other way, holding on to the next coach first reverse: save next, flip the arrow
two friends on a road, one walking twice as fast: when the fast one finishes, the slow one is halfway slow and fast pointers: 1 step and 2 steps
a circular running track: the faster runner laps the slower one Floyd's cycle detection: they meet only if there is a loop

Q1: Reverse a linked list in place

Problem. Reverse the list by changing the next arrows (no new nodes, no copying data) and return the new head.

Think out loud.

  • 1 -> 2 -> 3 -> 4 -> 5 -> NULL → 5 -> 4 -> 3 -> 2 -> 1 -> NULL; the new head is the old last node.
  • Edge cases: empty list, one node, two nodes.

The obvious attempt: flip, then follow next

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};
struct Node *build(int n);              /* 1 -> 2 -> ... -> n */
void print_list(struct Node *head);
void free_list(struct Node *head);

struct Node *reverse(struct Node *head) {
    struct Node *prev = NULL, *curr = head;
    while (curr != NULL) {
        curr->next = prev;      /* flip the arrow */
        prev = curr;
        curr = curr->next;      /* move on */
    }
    return prev;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        struct Node *head = build(n);
        print_list(head);
        head = reverse(head);
        print_list(head);
        free_list(head);
    }
    return 0;
}

/* ── helpers (same as episode 26) ── */
struct Node *build(int n) {
    struct Node *head = NULL;
    for (int v = n; v >= 1; v--) {      /* add at the front, n first */
        struct Node *p = malloc(sizeof *p);
        if (p == NULL) exit(1);
        p->data = v;
        p->next = head;
        head = p;
    }
    return head;
}

void print_list(struct Node *head) {
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->data);
    printf("NULL\n");
}

void free_list(struct Node *head) {
    while (head != NULL) {
        struct Node *next = head->next;
        free(head);
        head = next;
    }
}

Input: 5

1 -> 2 -> 3 -> 4 -> 5 -> NULL
1 -> NULL

Why it failed

curr->next = prev; overwrites the only pointer to the rest of the list. Then curr = curr->next; follows the arrow we just flipped, to prev (NULL), and the loop ends after one node. Nodes 2 to 5 can no longer be reached: they are lost and leaked.

The fix: save next first (prev, curr, next)

Four steps per node, in this order: save next = curr->next, flip curr->next = prev, move prev = curr, move curr = next. When curr is NULL, prev is the new head.

Step prev curr List so far
start NULL 1 1 -> 2 -> 3 -> 4 -> 5
after node 1 1 2 1 -> NULL, rest 2 -> 3 -> 4 -> 5
after node 2 2 3 2 -> 1 -> NULL, rest 3 -> 4 -> 5
… … … …
after node 5 5 NULL 5 -> 4 -> 3 -> 2 -> 1 -> NULL
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};
struct Node *build(int n);              /* 1 -> 2 -> ... -> n */
void print_list(struct Node *head);
void free_list(struct Node *head);

struct Node *reverse(struct Node *head) {
    struct Node *prev = NULL, *curr = head;
    while (curr != NULL) {
        struct Node *next = curr->next;   /* 1. save the rest */
        curr->next = prev;                /* 2. flip the arrow */
        prev = curr;                      /* 3. move prev */
        curr = next;                      /* 4. move curr */
    }
    return prev;                          /* the new head */
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        struct Node *head = build(n);
        print_list(head);
        head = reverse(head);
        print_list(head);
        free_list(head);
    }
    return 0;
}

/* ── helpers (same as episode 26) ── */
struct Node *build(int n) {
    struct Node *head = NULL;
    for (int v = n; v >= 1; v--) {      /* add at the front, n first */
        struct Node *p = malloc(sizeof *p);
        if (p == NULL) exit(1);
        p->data = v;
        p->next = head;
        head = p;
    }
    return head;
}

void print_list(struct Node *head) {
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->data);
    printf("NULL\n");
}

void free_list(struct Node *head) {
    while (head != NULL) {
        struct Node *next = head->next;
        free(head);
        head = next;
    }
}

Input: 5 / 1 / 0 / 2 (one list size per line; each list is printed before and after)

1 -> 2 -> 3 -> 4 -> 5 -> NULL
5 -> 4 -> 3 -> 2 -> 1 -> NULL
1 -> NULL
1 -> NULL
NULL
NULL
1 -> 2 -> NULL
2 -> 1 -> NULL

Complexity: O(n) time (each node once), O(1) extra space (three pointers). A recursive version (practice question 3) also works but uses O(n) stack, which can overflow for very long lists.

Q2: Find the middle node in one pass

Problem. Return the middle node. For an even length, return the second of the two middles (the usual interview rule). One pass.

Think out loud.

  • 1 -> 2 -> 3 -> 4 -> 5 → 3; 1 -> 2 -> 3 -> 4 → 3 (middles 2 and 3, take the second).
  • Counting n and then walking n/2 works, but takes two passes.
  • Edge cases: even length, one node, two nodes, empty list.

Idea: slow and fast pointers (also called the two-pointer or runner technique). Both start at head; each round slow moves 1 node and fast moves 2. When fast reaches the end, slow has gone half as far.

The obvious attempt: while (fast->next != NULL)

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};
struct Node *build(int n);              /* 1 -> 2 -> ... -> n */
void print_list(struct Node *head);
void free_list(struct Node *head);

struct Node *middle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast->next != NULL) {
        slow = slow->next;          /* 1 step */
        fast = fast->next->next;    /* 2 steps */
    }
    return slow;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        struct Node *head = build(n);
        printf("n=%d: middle ", n);
        fflush(stdout);
        struct Node *m = middle(head);
        if (m == NULL) printf("none (empty list)\n");
        else           printf("%d\n", m->data);
        free_list(head);
    }
    return 0;
}

/* ── helpers (same as episode 26) ── */
struct Node *build(int n) {
    struct Node *head = NULL;
    for (int v = n; v >= 1; v--) {      /* add at the front, n first */
        struct Node *p = malloc(sizeof *p);
        if (p == NULL) exit(1);
        p->data = v;
        p->next = head;
        head = p;
    }
    return head;
}

void print_list(struct Node *head) {
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->data);
    printf("NULL\n");
}

void free_list(struct Node *head) {
    while (head != NULL) {
        struct Node *next = head->next;
        free(head);
        head = next;
    }
}

Input: 5 / 4

n=5: middle 3
n=4: middle 
Segmentation fault

Why it failed

With 4 nodes, fast goes 1 → 3 → NULL (from 3, two steps pass 4 and land on NULL). The next check reads fast->next with fast == NULL: a NULL pointer dereference, undefined behaviour, and Linux stops the program with a segmentation fault. An empty list crashes at once, since head itself is NULL.

The fix: check fast before fast->next

while (fast != NULL && fast->next != NULL). && short-circuits: if the left side is false, the right side is never evaluated, so fast->next is never read when fast is NULL.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};
struct Node *build(int n);              /* 1 -> 2 -> ... -> n */
void print_list(struct Node *head);
void free_list(struct Node *head);

struct Node *middle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;          /* 1 step */
        fast = fast->next->next;    /* 2 steps */
    }
    return slow;                    /* even length: the 2nd middle */
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        struct Node *head = build(n);
        printf("n=%d: middle ", n);
        fflush(stdout);
        struct Node *m = middle(head);
        if (m == NULL) printf("none (empty list)\n");
        else           printf("%d\n", m->data);
        free_list(head);
    }
    return 0;
}

/* ── helpers (same as episode 26) ── */
struct Node *build(int n) {
    struct Node *head = NULL;
    for (int v = n; v >= 1; v--) {      /* add at the front, n first */
        struct Node *p = malloc(sizeof *p);
        if (p == NULL) exit(1);
        p->data = v;
        p->next = head;
        head = p;
    }
    return head;
}

void print_list(struct Node *head) {
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->data);
    printf("NULL\n");
}

void free_list(struct Node *head) {
    while (head != NULL) {
        struct Node *next = head->next;
        free(head);
        head = next;
    }
}

Input: 5 / 4 / 1 / 2 / 0

n=5: middle 3
n=4: middle 3
n=1: middle 1
n=2: middle 2
n=0: middle none (empty list)

For the first middle of an even-length list, start fast at head->next (when head isn't NULL).

Complexity: O(n) time, one pass (about n/2 rounds); O(1) extra space.

Q3: Detect a loop

Problem. Does the list have a loop (a cycle): does some node's next point back to an earlier node, so there is no NULL at the end? Input: n k builds 1 -> … -> n and points node n back at node k (k = 0: no loop). All nodes are kept in an array nodes[] so they can be freed even when there is a loop.

Think out loud.

  • 5 3: 1 -> 2 -> 3 -> 4 -> 5 -> (back to 3) → loop. 5 0 → no loop.
  • Edge cases: the loop goes back to the head (5 1), to the middle (5 3), a node pointing at itself (1 1, 5 5), an empty list (0 0).

The obvious attempt: "a loop comes back to head"

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};
struct Node *nodes[100];                /* every node, so we can free them */
struct Node *build_loop(int n, int k);  /* 1..n, then n -> node k (0 = no loop) */
void free_all(int n);

int has_loop(struct Node *head) {       /* a loop must come back to head? */
    if (head == NULL) return 0;
    for (struct Node *p = head->next; p != NULL; p = p->next)
        if (p == head) return 1;
    return 0;
}

int main() {
    int n, k;
    while (scanf("%d %d", &n, &k) == 2 && n >= 0 && n <= 100 && k >= 0 && k <= n) {
        struct Node *head = build_loop(n, k);
        printf("n=%d, last -> node %d: %s\n", n, k, has_loop(head) ? "loop" : "no loop");
        fflush(stdout);
        free_all(n);
    }
    return 0;
}

/* ── helpers ── */
struct Node *build_loop(int n, int k) {
    for (int i = 0; i < n; i++) {
        nodes[i] = malloc(sizeof *nodes[i]);
        if (nodes[i] == NULL) exit(1);
        nodes[i]->data = i + 1;
        nodes[i]->next = NULL;
        if (i > 0) nodes[i - 1]->next = nodes[i];
    }
    if (n > 0 && k > 0) nodes[n - 1]->next = nodes[k - 1];   /* make the loop */
    return n > 0 ? nodes[0] : NULL;
}

void free_all(int n) {
    for (int i = 0; i < n; i++) free(nodes[i]);
}

Input: 5 0 / 5 1 / 5 3

The first two answers are right (no loop, loop), but with 5 3 the program never finishes. The SyntaxPilot compiler stops a program after 25 seconds and reports Time Limit Exceeded; on your own computer it would run until you press Ctrl+C.

n=5, last -> node 0: no loop
n=5, last -> node 1: loop
(Time Limit Exceeded: the third list never finishes)

Why it failed

A loop can come back to any node, not only the head. In 5 3 the walk goes 1, 2, 3, 4, 5, 3, 4, 5, 3, … forever: it never sees head and never sees NULL.

The fix: Floyd's cycle detection (tortoise and hare)

slow moves 1 step, fast moves 2.

  • No loop: fast reaches NULL → no loop.
  • Loop: both end up going round the loop. Each round, fast gains exactly one node on slow, so the gap shrinks by one every round and fast can't jump over slow: they must meet, within at most (loop length) rounds after slow enters the loop. Meeting means loop.

We compare pointers (slow == fast: the same node), not data (two nodes can hold the same number).

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};
struct Node *nodes[100];                /* every node, so we can free them */
struct Node *build_loop(int n, int k);  /* 1..n, then n -> node k (0 = no loop) */
void free_all(int n);

int has_loop(struct Node *head) {       /* Floyd: tortoise and hare */
    struct Node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;              /* 1 step */
        fast = fast->next->next;        /* 2 steps */
        if (slow == fast) return 1;     /* the hare caught up: a loop */
    }
    return 0;                           /* the hare reached NULL */
}

int main() {
    int n, k;
    while (scanf("%d %d", &n, &k) == 2 && n >= 0 && n <= 100 && k >= 0 && k <= n) {
        struct Node *head = build_loop(n, k);
        printf("n=%d, last -> node %d: %s\n", n, k, has_loop(head) ? "loop" : "no loop");
        fflush(stdout);
        free_all(n);
    }
    return 0;
}

/* ── helpers ── */
struct Node *build_loop(int n, int k) {
    for (int i = 0; i < n; i++) {
        nodes[i] = malloc(sizeof *nodes[i]);
        if (nodes[i] == NULL) exit(1);
        nodes[i]->data = i + 1;
        nodes[i]->next = NULL;
        if (i > 0) nodes[i - 1]->next = nodes[i];
    }
    if (n > 0 && k > 0) nodes[n - 1]->next = nodes[k - 1];   /* make the loop */
    return n > 0 ? nodes[0] : NULL;
}

void free_all(int n) {
    for (int i = 0; i < n; i++) free(nodes[i]);
}

Input: 5 0 / 5 3 / 5 1 / 1 1 / 1 0 / 0 0 / 2 2

n=5, last -> node 0: no loop
n=5, last -> node 3: loop
n=5, last -> node 1: loop
n=1, last -> node 1: loop
n=1, last -> node 0: no loop
n=0, last -> node 0: no loop
n=2, last -> node 2: loop

Complexity: O(n) time, O(1) extra space. The other common approach, remembering every visited address in a hash set, is also O(n) time but needs O(n) extra memory.

Complexity summary

Question Time Extra space
Reverse (prev, curr, next) O(n) O(1)
Reverse (recursive) O(n) O(n) stack
Middle (count, then walk) O(n), two passes O(1)
Middle (slow and fast) O(n), one pass O(1)
Loop (visited set) O(n) O(n)
Loop (Floyd) O(n) O(1)

The safe condition for any two-step walk: fast != NULL && fast->next != NULL.

Common mistakes (and the real results)

Mistake What happens Why Fix
curr->next = prev; curr = curr->next; 1 -> NULL, nodes 2..5 lost followed the flipped arrow save next first
return head; after reversing 1 -> NULL the old head is now the last node return prev;
while (fast->next != NULL) Segmentation fault for even n and for an empty list fast became NULL fast != NULL && fast->next != NULL
"a loop must come back to head" Time Limit Exceeded the loop can skip the head Floyd
if (slow->data == fast->data) false "loop" on 1 -> 1 -> 2 equal data, different nodes slow == fast
free_list(head) on a list with a loop runs forever / double free there is no NULL break the loop first, or keep the nodes in an array

Your turn: where does the loop start? (solution)

Problem. If the list has a loop, return the node where the loop starts; NULL if there is no loop. 5 3 → 3.

Idea. Run Floyd until slow and fast meet. Put one pointer back at head and move both one step at a time; they meet at the start of the loop.

Why it works. Let a = steps from head to the loop start, L = loop length, and b = steps from the loop start to the meeting point. When they meet, slow has walked a + b, and fast has walked 2(a + b), which is a + b plus some whole number of laps: a + b = m·L. So a = m·L − b: walking a steps from the meeting point lands exactly on the loop start, which is also where a pointer walking a steps from head arrives.

#include <stdio.h>
#include <stdlib.h>

struct Node { int data; struct Node *next; };
struct Node *nodes[100];

struct Node *loop_start(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) {                 /* they met inside the loop */
            struct Node *p = head;
            while (p != slow) { p = p->next; slow = slow->next; }
            return p;                       /* both one step at a time: meet at the start */
        }
    }
    return NULL;                            /* no loop */
}

int main() {
    int n, k;
    while (scanf("%d %d", &n, &k) == 2 && n >= 1 && n <= 100 && k >= 0 && k <= n) {
        for (int i = 0; i < n; i++) {
            nodes[i] = malloc(sizeof *nodes[i]);
            if (nodes[i] == NULL) return 1;
            nodes[i]->data = i + 1;
            nodes[i]->next = NULL;
            if (i > 0) nodes[i - 1]->next = nodes[i];
        }
        if (k > 0) nodes[n - 1]->next = nodes[k - 1];
        struct Node *s = loop_start(nodes[0]);
        if (s) printf("loop starts at %d\n", s->data);
        else   printf("no loop\n");
        for (int i = 0; i < n; i++) free(nodes[i]);
    }
    return 0;
}

Input: 5 3 / 5 1 / 5 5 / 5 0 / 1 1 / 7 4

loop starts at 3
loop starts at 1
loop starts at 5
no loop
loop starts at 1
loop starts at 4

O(n) time, O(1) extra space.

Practice questions (with solutions)

1. The length of the loop.

Solution

After slow and fast meet, they are inside the loop: go round once and count.

#include <stdio.h>
#include <stdlib.h>

struct Node { int data; struct Node *next; };
struct Node *nodes[100];

int loop_length(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) {                  /* inside the loop: go round once */
            int len = 1;
            for (struct Node *p = slow->next; p != slow; p = p->next) len++;
            return len;
        }
    }
    return 0;                                /* no loop */
}

int main() {
    int n, k;
    while (scanf("%d %d", &n, &k) == 2 && n >= 1 && n <= 100 && k >= 0 && k <= n) {
        for (int i = 0; i < n; i++) {
            nodes[i] = malloc(sizeof *nodes[i]);
            if (nodes[i] == NULL) return 1;
            nodes[i]->data = i + 1;
            nodes[i]->next = NULL;
            if (i > 0) nodes[i - 1]->next = nodes[i];
        }
        if (k > 0) nodes[n - 1]->next = nodes[k - 1];
        printf("n=%d k=%d: loop length %d\n", n, k, loop_length(nodes[0]));
        for (int i = 0; i < n; i++) free(nodes[i]);
    }
    return 0;
}

Input: 5 3 / 5 1 / 5 5 / 5 0 / 7 4

n=5 k=3: loop length 3
n=5 k=1: loop length 5
n=5 k=5: loop length 1
n=5 k=0: loop length 0
n=7 k=4: loop length 4

O(n) time, O(1) space.

2. Is a linked list a palindrome?

Solution

Find the middle (Q2), reverse the second half (Q1), compare it with the first half, then reverse it back so the caller's list is unchanged.

#include <stdio.h>
#include <stdlib.h>

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

struct Node *reverse(struct Node *head) {
    struct Node *prev = NULL, *curr = head;
    while (curr != NULL) {
        struct Node *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

int is_palindrome(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {     /* slow = the (second) middle */
        slow = slow->next;
        fast = fast->next->next;
    }
    struct Node *second = reverse(slow);             /* reverse the second half */
    int ok = 1;
    for (struct Node *a = head, *b = second; b != NULL; a = a->next, b = b->next)
        if (a->data != b->data) { ok = 0; break; }
    reverse(second);                                 /* put the list back */
    return ok;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n >= 0) {
        struct Node *head = NULL, *tail = NULL;
        for (int i = 0; i < n; i++) {
            struct Node *x = malloc(sizeof *x);
            if (x == NULL) return 1;
            if (scanf("%d", &x->data) != 1) x->data = 0;
            x->next = NULL;
            if (head == NULL) head = x; else tail->next = x;
            tail = x;
        }
        printf("%s\n", is_palindrome(head) ? "palindrome" : "not a palindrome");
        while (head != NULL) { struct Node *t = head->next; free(head); head = t; }
    }
    return 0;
}

Input (n, then n numbers): 5 / 1 2 3 2 1, 4 / 1 2 2 1, 4 / 1 2 3 1, 1 / 7, 0, 2 / 4 5

palindrome
palindrome
not a palindrome
palindrome
palindrome
not a palindrome

O(n) time, O(1) extra space.

3. Reverse a list recursively.

Solution

Reverse the rest of the list; then the old second node (head->next) is the last node of the reversed rest, so point it back at head, and end the list at head.

#include <stdio.h>
#include <stdlib.h>

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

struct Node *reverse_rec(struct Node *head) {
    if (head == NULL || head->next == NULL) return head;   /* 0 or 1 node */
    struct Node *new_head = reverse_rec(head->next);      /* reverse the rest */
    head->next->next = head;                               /* the old 2nd node points back */
    head->next = NULL;
    return new_head;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n >= 0) {
        struct Node *head = NULL;
        for (int v = n; v >= 1; v--) {
            struct Node *x = malloc(sizeof *x);
            if (x == NULL) return 1;
            x->data = v; x->next = head; head = x;
        }
        head = reverse_rec(head);
        for (struct Node *p = head; p != NULL; p = p->next) printf("%d -> ", p->data);
        printf("NULL\n");
        while (head != NULL) { struct Node *t = head->next; free(head); head = t; }
    }
    return 0;
}

Input: 5 / 1 / 0 / 2

5 -> 4 -> 3 -> 2 -> 1 -> NULL
1 -> NULL
NULL
2 -> 1 -> NULL

O(n) time, O(n) stack space (one call per node).

Quick quiz

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    struct Node v[6];
    for (int i = 0; i < 6; i++) { v[i].data = i + 1; v[i].next = i < 5 ? &v[i + 1] : NULL; }
    struct Node *head = &v[0];
    struct Node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    printf("%d\n", slow->data);
    return 0;
}

What does it print? (A) 3 (B) 4 (C) 6 (D) Segmentation fault

Answer

(B) 4 (real output: 4). fast goes 1 → 3 → 5 → NULL while slow goes 1 → 2 → 3 → 4. For an even length, slow stops on the second middle. No crash: fast != NULL is checked first.

Interview questions

  1. Reverse a singly linked list in place. prev, curr, next: save, flip, move, move; return prev. O(n), O(1).
  2. Why do you need a third pointer? Flipping curr->next destroys the only link to the rest of the list.
  3. Find the middle in one pass. Slow 1 step, fast 2 steps.
  4. Which middle does while (fast && fast->next) return for an even length? The second; start fast at head->next for the first.
  5. Detect a cycle in a linked list. Floyd's tortoise and hare: they meet if and only if there is a cycle. O(n), O(1).
  6. Why must they meet, and why can't fast jump over slow? Inside the loop the gap shrinks by exactly 1 each round.
  7. Find where the cycle starts. After meeting, move one pointer to head and step both by one.
  8. Find the length of the cycle. From the meeting point, go round once counting.
  9. Is a linked list a palindrome, in O(1) extra space? Middle, reverse the second half, compare, restore.
  10. Recursive vs iterative reverse? Same O(n) time; recursion uses O(n) stack.

Glossary

Term Meaning Example
Reverse in place Reverse by changing links, without new nodes Q1
prev / curr / next The node before, the current node, the saved rest Q1
Slow and fast pointers Two pointers walking at 1 and 2 steps per round Q2, Q3
Two-pointer technique Solving a problem with two moving positions middle, loop
Middle node The node halfway along; the 2nd middle for even lengths 1..4 → 3
Short-circuit evaluation && skips its right side when the left is false fast != NULL && fast->next != NULL
NULL dereference Reading through a NULL pointer: undefined behaviour NULL->next
Segmentation fault The OS stops a program touching memory it doesn't own Q2's bug
Loop / cycle A node's next points back to an earlier node 5 -> 3
Floyd's cycle detection Tortoise (1 step) and hare (2 steps) meet iff there is a cycle Q3
Time Limit Exceeded The online compiler stopped a program that ran too long Q3's bug
Infinite loop A loop whose condition never becomes false waiting for head
Pointer comparison p == q: the same address, the same node slow == fast
Hash set A structure for "seen before?" in O(1) average the O(n)-space way
Palindrome Reads the same both ways 1 2 3 2 1
Recursion depth How many calls are active at once n for recursive reverse
valgrind A tool that reports memory errors and leaks every fixed program

Summary

  • Reverse: save next, flip curr->next = prev, move prev, move curr; return prev. O(n) time, O(1) space.
  • Middle: slow 1 step, fast 2 steps; while (fast != NULL && fast->next != NULL); even length gives the second middle.
  • Loop: a loop can skip the head, so "wait for head" or "wait for NULL" can run forever. Floyd's tortoise and hare meet if and only if there is a loop: O(n) time, O(1) space. Compare pointers, not data.
  • After they meet, one pointer back at head and both one step at a time finds where the loop starts.

Next episode: Stack and queue questions: a stack with an array (overflow and underflow), balanced brackets, and a circular queue.