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:
fastreaches NULL → no loop. - Loop: both end up going round the loop. Each round,
fastgains exactly one node onslow, so the gap shrinks by one every round andfastcan't jump overslow: they must meet, within at most (loop length) rounds afterslowenters 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
- Reverse a singly linked list in place. prev, curr, next: save, flip, move, move; return prev. O(n), O(1).
- Why do you need a third pointer? Flipping
curr->nextdestroys the only link to the rest of the list. - Find the middle in one pass. Slow 1 step, fast 2 steps.
- Which middle does
while (fast && fast->next)return for an even length? The second; startfastathead->nextfor the first. - 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).
- Why must they meet, and why can't fast jump over slow? Inside the loop the gap shrinks by exactly 1 each round.
- Find where the cycle starts. After meeting, move one pointer to head and step both by one.
- Find the length of the cycle. From the meeting point, go round once counting.
- Is a linked list a palindrome, in O(1) extra space? Middle, reverse the second half, compare, restore.
- 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, flipcurr->next = prev, moveprev, movecurr; returnprev. 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.