These are the notes for C++ Coding Questions, episode 23, placement practice for people who finished the SyntaxPilot C++ course. Part two of linked lists, and three of the most asked interview questions: reversing a list in place (why flipping the arrow first loses the list), finding the middle in one pass with slow and fast pointers (and the even-length crash), and detecting a cycle with Floyd's algorithm (and why "walk until we see head again" never ends).
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 g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program that runs too long (Time Limit Exceeded, TLE), like an online judge, and shows Segmentation fault when a program crashes.
Real-life pictures
| In real life | In C++ |
|---|---|
| A ration shop queue, everyone holding the shoulder in front | a linked list: each node points to the next |
| The door moves to the other end: everyone turns around | reverse the list |
| Letting go and turning before looking back: who was behind me? | cur->next = prev before saving next: the rest is lost |
| Look back first, then let go and turn | save nxt, flip, step |
| Two friends walk a path, one takes 2 steps for every 1 | slow and fast pointers |
| When the fast friend reaches the end, the slow one is halfway | the middle in one pass |
| The fast friend must check both next steps exist | fast != nullptr && fast->next != nullptr |
| A road that ends at a wall vs one that ends in a roundabout | nullptr vs a cycle |
| Two runners on a circular track: the faster one always laps the slower | Floyd's algorithm (tortoise and hare) |
Refresher: the helpers every program uses
All three questions reuse the helpers from episode 22: a Node struct, readList() (reads n and n numbers and builds the list with a tail pointer), print(head) (walks with cur), and freeList(head) (saves next before delete).
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* readList() { // n, then n numbers
int n;
cin >> n;
Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Node* node = new Node{x, nullptr};
if (head == nullptr) head = node;
else tail->next = node;
tail = node;
}
return head;
}
void print(Node* head) {
for (Node* cur = head; cur != nullptr; cur = cur->next)
cout << cur->data << " -> ";
cout << "NULL\n";
}
void freeList(Node*& head) {
while (head != nullptr) {
Node* nxt = head->next;
delete head;
head = nxt;
}
}
For every question, check two edge cases first: the empty list (head == nullptr) and a list with one node.
Q1: Reverse a linked list in place
Problem. Read a list and print it, then reverse it in place (no new nodes: only the next arrows change) and print it again.
| Input | Output (second line) |
|---|---|
10 20 30 40 |
40 -> 30 -> 20 -> 10 -> NULL |
10 |
10 -> NULL |
| empty | NULL |
Think out loud. Every arrow must point backwards, and the old last node becomes the new head. Walk with cur, and keep prev, the node before it (it starts as nullptr, which the old head will point to).
The obvious attempt: flip the arrow, then follow it
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* readList() { // n, then n numbers
int n;
cin >> n;
Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Node* node = new Node{x, nullptr};
if (head == nullptr) head = node;
else tail->next = node;
tail = node;
}
return head;
}
void print(Node* head) {
for (Node* cur = head; cur != nullptr; cur = cur->next)
cout << cur->data << " -> ";
cout << "NULL\n";
}
void freeList(Node*& head) {
while (head != nullptr) {
Node* nxt = head->next;
delete head;
head = nxt;
}
}
Node* reverse(Node* head) {
Node* prev = nullptr;
Node* cur = head;
while (cur != nullptr) {
cur->next = prev; // flip the arrow
prev = cur;
cur = cur->next; // move on to the next box
}
return prev; // the old last box
}
int main() {
Node* head = readList();
print(head);
head = reverse(head);
print(head);
freeList(head);
return 0;
}
Input:
4
10 20 30 40
Output:
10 -> 20 -> 30 -> 40 -> NULL
10 -> NULL
The reversed list is just 10. 20, 30 and 40 vanished.
Why it fails
cur->next = prev; makes 10 point to nullptr. Then cur = cur->next; follows the new arrow: cur becomes nullptr, and the loop ends after one node. The only arrow to 20 was overwritten, so 20, 30 and 40 are lost (and leaked: freeList can only free 10).
Fix: remember, flip, step
- Remember the next node:
Node* nxt = cur->next; - Flip the arrow:
cur->next = prev; - Step forward:
prev = cur; cur = nxt;
When cur reaches nullptr, prev is the old last node: the new head.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* readList() { // n, then n numbers
int n;
cin >> n;
Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Node* node = new Node{x, nullptr};
if (head == nullptr) head = node;
else tail->next = node;
tail = node;
}
return head;
}
void print(Node* head) {
for (Node* cur = head; cur != nullptr; cur = cur->next)
cout << cur->data << " -> ";
cout << "NULL\n";
}
void freeList(Node*& head) {
while (head != nullptr) {
Node* nxt = head->next;
delete head;
head = nxt;
}
}
Node* reverse(Node* head) {
Node* prev = nullptr;
Node* cur = head;
while (cur != nullptr) {
Node* nxt = cur->next; // 1. remember who is next
cur->next = prev; // 2. flip the arrow
prev = cur; // 3. step forward
cur = nxt;
}
return prev; // the old last box
}
int main() {
Node* head = readList();
print(head);
head = reverse(head);
print(head);
freeList(head);
return 0;
}
Input:
4
10 20 30 40
Output:
10 -> 20 -> 30 -> 40 -> NULL
40 -> 30 -> 20 -> 10 -> NULL
Input:
1
10
Output:
10 -> NULL
10 -> NULL
Input 0:
NULL
NULL
With an empty list the loop never runs and prev (nullptr) is returned. One node: its arrow is flipped to nullptr, which it already was.
Trace for 10 20 30:
| Step | prev | cur | nxt | after the flip |
|---|---|---|---|---|
| 1 | nullptr | 10 | 20 | NULL <- 10 · 20 -> 30 |
| 2 | 10 | 20 | 30 | NULL <- 10 <- 20 · 30 |
| 3 | 20 | 30 | nullptr | NULL <- 10 <- 20 <- 30 |
| end | 30 | nullptr | head = prev = 30 |
Complexity. Time O(n), one walk. Space O(1): three pointers, however long the list is.
The recursive version (and why interviews prefer the loop)
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* readList() { // n, then n numbers
int n;
cin >> n;
Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Node* node = new Node{x, nullptr};
if (head == nullptr) head = node;
else tail->next = node;
tail = node;
}
return head;
}
void print(Node* head) {
for (Node* cur = head; cur != nullptr; cur = cur->next)
cout << cur->data << " -> ";
cout << "NULL\n";
}
void freeList(Node*& head) {
while (head != nullptr) {
Node* nxt = head->next;
delete head;
head = nxt;
}
}
Node* reverseRec(Node* head) {
if (head == nullptr || head->next == nullptr) return head; // 0 or 1 box
Node* newHead = reverseRec(head->next); // reverse the rest
head->next->next = head; // the box after me now points to me
head->next = nullptr;
return newHead;
}
int main() {
Node* head = readList();
head = reverseRec(head);
print(head);
freeList(head);
return 0;
}
Input:
4
10 20 30 40
Output:
40 -> 30 -> 20 -> 10 -> NULL
It is shorter, but every node adds a stack frame: O(n) space, and a list of a few million nodes can overflow the call stack. The loop uses O(1).
Q2: The middle of a linked list, in one pass
Problem. Print the middle value. If the count is even there are two middles: print the second one. Print empty list for an empty list.
| Input | Output |
|---|---|
10 20 30 40 50 |
middle: 30 |
10 20 30 40 50 60 |
middle: 40 |
10 |
middle: 10 |
| empty | empty list |
Think out loud. Counting the nodes and then walking n / 2 works, but walks the list twice. Copying into a vector works too, but needs O(n) extra memory:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int& x : v) cin >> x;
if (n == 0) cout << "empty list\n";
else cout << "middle: " << v[n / 2] << "\n"; // second middle for even n
return 0;
}
Input:
6
10 20 30 40 50 60
Output:
middle: 40
The interview answer is one pass and O(1) space: slow moves 1 step, fast moves 2. When fast reaches the end, slow has gone half as far.
The obvious attempt: while (fast->next != nullptr)
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* readList() { // n, then n numbers
int n;
cin >> n;
Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Node* node = new Node{x, nullptr};
if (head == nullptr) head = node;
else tail->next = node;
tail = node;
}
return head;
}
void print(Node* head) {
for (Node* cur = head; cur != nullptr; cur = cur->next)
cout << cur->data << " -> ";
cout << "NULL\n";
}
void freeList(Node*& head) {
while (head != nullptr) {
Node* nxt = head->next;
delete head;
head = nxt;
}
}
Node* middle(Node* head) {
Node* slow = head; // 1 step at a time
Node* fast = head; // 2 steps at a time
while (fast->next != nullptr) { // can fast take 2 more steps?
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
int main() {
Node* head = readList();
Node* mid = middle(head);
if (mid == nullptr) cout << "empty list\n";
else cout << "middle: " << mid->data << "\n";
freeList(head);
return 0;
}
Input:
5
10 20 30 40 50
Output:
middle: 30
Input:
6
10 20 30 40 50 60
Output:
Segmentation fault
Why it fails
| Count | fast visits | then |
|---|---|---|
| 5 (odd) | 10 → 30 → 50 | 50's next is nullptr: the loop stops |
| 6 (even) | 10 → 30 → 50 → nullptr (60's next) |
the check reads fast->next with fast == nullptr: crash |
With an odd count fast lands on the last node; with an even count it jumps past it. The empty list crashes too: fast is nullptr from the start.
Fix: check fast itself first
while (fast != nullptr && fast->next != nullptr). && evaluates left to right and stops at the first false (short-circuit evaluation), so nullptr->next is never read.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* readList() { // n, then n numbers
int n;
cin >> n;
Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Node* node = new Node{x, nullptr};
if (head == nullptr) head = node;
else tail->next = node;
tail = node;
}
return head;
}
void print(Node* head) {
for (Node* cur = head; cur != nullptr; cur = cur->next)
cout << cur->data << " -> ";
cout << "NULL\n";
}
void freeList(Node*& head) {
while (head != nullptr) {
Node* nxt = head->next;
delete head;
head = nxt;
}
}
Node* middle(Node* head) {
Node* slow = head; // 1 step at a time
Node* fast = head; // 2 steps at a time
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
int main() {
Node* head = readList();
Node* mid = middle(head);
if (mid == nullptr) cout << "empty list\n";
else cout << "middle: " << mid->data << "\n";
freeList(head);
return 0;
}
Input:
6
10 20 30 40 50 60
Output:
middle: 40
Input:
5
10 20 30 40 50
Output:
middle: 30
Input:
1
10
Output:
middle: 10
Input 0:
empty list
Complexity. Time O(n) (fast walks the list once; slow walks half). Space O(1).
First vs second middle. Start fast at head->next instead of head and the loop stops one step earlier: for an even count slow ends on the first middle. That version is the one you want for splitting a list into two halves (merge sort on lists, the palindrome check below).
Q3: Does the list have a cycle?
Problem. A bug linked the last node back into the list, so walking it never ends: a cycle. Print cycle or no cycle. The test program builds the cycle on purpose: after n numbers it reads pos and links the last node back to node number pos (-1 = no link).
pos = 0: 10 -> 20 -> 30 -> 40 -> 50 -> back to 10 a full ring
pos = 2: 10 -> 20 -> 30 -> 40 -> 50 -> back to 30 shaped like a 6 (the Greek letter rho, ρ)
pos = -1: 10 -> 20 -> 30 -> 40 -> 50 -> NULL no cycle
main keeps every node in a vector<Node*> box and deletes each one exactly once at the end. freeList would never reach nullptr on a list with a cycle.
The obvious attempt: walk until we come back to head
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* next;
};
bool hasCycle(Node* head) {
if (head == nullptr) return false;
for (Node* cur = head->next; cur != nullptr; cur = cur->next)
if (cur == head) return true; // back at the start: a cycle
return false; // reached the end: no cycle
}
int main() {
int n, pos;
cin >> n;
vector<Node*> box(n);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
box[i] = new Node{x, nullptr};
if (i > 0) box[i - 1]->next = box[i];
}
cin >> pos; // last box links to box pos
if (n > 0 && pos >= 0) box[n - 1]->next = box[pos]; // -1: none
Node* head = (n > 0) ? box[0] : nullptr;
cout << (hasCycle(head) ? "cycle\n" : "no cycle\n");
for (Node* b : box) delete b; // free each box exactly once
return 0;
}
Input: pos = 0 (a full ring):
cycle
Input: pos = 2 (the 6 shape):
(no output: the program never ends) → Time Limit Exceeded
Why it fails
With pos = 2 the walk goes 10, 20, then 30, 40, 50, 30, 40, 50, ... forever. It never comes back to 10 (the head is not part of the loop) and never reaches nullptr, so neither return is ever reached.
Another way that works: remember every node. Put each node's address in an unordered_set<Node*>; the first address seen twice means a cycle. That is O(n) time but O(n) extra memory.
Fix: Floyd's algorithm (the tortoise and the hare)
slow moves 1 step, fast moves 2. If fast reaches nullptr, there is no cycle. If there is a cycle, both end up inside it and fast gains exactly one node on slow per step; the gap shrinks by one each time, so it must reach zero: they meet, and fast can never jump over slow.
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* next;
};
bool hasCycle(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next; // 1 step
fast = fast->next->next; // 2 steps
if (slow == fast) return true; // fast caught up: a loop
}
return false; // fast reached the end
}
int main() {
int n, pos;
cin >> n;
vector<Node*> box(n);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
box[i] = new Node{x, nullptr};
if (i > 0) box[i - 1]->next = box[i];
}
cin >> pos; // last box links to box pos
if (n > 0 && pos >= 0) box[n - 1]->next = box[pos]; // -1: none
Node* head = (n > 0) ? box[0] : nullptr;
cout << (hasCycle(head) ? "cycle\n" : "no cycle\n");
for (Node* b : box) delete b; // free each box exactly once
return 0;
}
Input: pos = 2:
cycle
Input: pos = -1:
no cycle
Input: one node linked to itself:
cycle
Input: the empty list:
no cycle
Input: pos = 0:
cycle
Complexity. Time O(n): without a cycle fast reaches the end; with one, slow enters the loop within n steps and fast catches it within one lap of the loop. Space O(1).
Your turn: where does the cycle start?
After slow meets fast, put slow back at head and move both one step at a time. Where they meet is the first node of the cycle.
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* cycleStart(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { // they met inside the loop
slow = head; // one goes back to the start
while (slow != fast) { // both walk 1 step at a time
slow = slow->next;
fast = fast->next;
}
return slow; // where they meet: the loop's first box
}
}
return nullptr; // no cycle
}
int main() {
int n, pos;
cin >> n;
vector<Node*> box(n);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
box[i] = new Node{x, nullptr};
if (i > 0) box[i - 1]->next = box[i];
}
cin >> pos;
if (n > 0 && pos >= 0) box[n - 1]->next = box[pos];
Node* s = cycleStart(n > 0 ? box[0] : nullptr);
if (s == nullptr) cout << "no cycle\n";
else cout << "cycle starts at " << s->data << "\n";
for (Node* b : box) delete b;
return 0;
}
Input: pos = 2:
cycle starts at 30
Input: pos = 0:
cycle starts at 10
Input: pos = 4 (50 points to itself):
cycle starts at 50
Input: pos = -1:
no cycle
Why it works. Let a = the number of steps from the head to the start of the cycle, and L = the length of the cycle. When they meet, say b steps into the cycle, slow has walked a + b and fast has walked twice that, 2(a + b). Fast walked some whole number k of extra laps: 2(a + b) = a + b + kL, so a + b = kL, which means a = kL − b. Now one pointer starts at the head and the other at the meeting point, both moving 1 step. After a steps the first is at the cycle's start. The second has walked a = kL − b steps from b steps into the cycle, which puts it at b + kL − b = kL steps into the cycle: exactly the start (whole laps change nothing). They meet there.
Complexity summary
| Question | Obvious attempt | Fixed | Time | Extra space |
|---|---|---|---|---|
| reverse | flip, then cur = cur->next: only 10 -> NULL |
save nxt first |
O(n) | O(1) |
| reverse (recursive) | head->next->next = head |
O(n) | O(n) stack | |
| middle | while (fast->next != nullptr): segfault for an even count |
fast != nullptr && first |
O(n) | O(1) |
| middle via a vector | v[n / 2] |
O(n) | O(n) | |
| cycle | wait to see head again: TLE on a 6 shape | Floyd: slow == fast |
O(n) | O(1) |
| cycle via a set | unordered_set<Node*> |
O(n) average | O(n) |
The theme: a few pointers moving at different speeds replace a whole extra copy of the list.
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
cur->next = prev; cur = cur->next; |
no error: only 10 -> NULL |
follows the flipped arrow | save nxt first |
forgetting head = reverse(head); |
the list prints as just the old head | head still points to the old first node, now the last |
use the returned new head |
while (fast->next != nullptr) |
Segmentation fault (even count, empty list) |
fast became nullptr |
fast != nullptr && fast->next != nullptr |
fast->next != nullptr && fast != nullptr |
Segmentation fault |
wrong order: fast->next is read first |
null check first |
walk until cur == head |
Time Limit Exceeded on a 6 shape |
the head is not inside the loop | Floyd |
freeList on a list with a cycle |
never ends, or a double free | it never reaches nullptr |
break the loop first, or free each node once |
comparing values instead of addresses (slow->data == fast->data) |
a false "cycle" on 1 2 1 2 |
two different nodes can hold equal values | compare pointers: slow == fast |
Mini project: merge two sorted lists
Merge two sorted lists into one sorted list without making new nodes, only relinking them. A dummy node (a fake first node on the stack) removes the special case for the head: we always append after tail, and the answer is dummy.next. Input: the first list (n and its numbers), then the second.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* readList() { // n, then n numbers
int n;
cin >> n;
Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Node* node = new Node{x, nullptr};
if (head == nullptr) head = node;
else tail->next = node;
tail = node;
}
return head;
}
void print(Node* head) {
for (Node* cur = head; cur != nullptr; cur = cur->next)
cout << cur->data << " -> ";
cout << "NULL\n";
}
void freeList(Node*& head) {
while (head != nullptr) {
Node* nxt = head->next;
delete head;
head = nxt;
}
}
Node* merge(Node* a, Node* b) {
Node dummy{0, nullptr}; // a fake first box: no head special case
Node* tail = &dummy;
while (a != nullptr && b != nullptr) {
if (a->data <= b->data) { tail->next = a; a = a->next; }
else { tail->next = b; b = b->next; }
tail = tail->next;
}
tail->next = (a != nullptr) ? a : b; // whatever is left is already sorted
return dummy.next;
}
int main() {
Node* a = readList();
Node* b = readList();
Node* m = merge(a, b); // no new boxes: the same ones relinked
print(m);
freeList(m);
return 0;
}
Input:
3
1 4 9
4
2 3 10 12
Output:
1 -> 2 -> 3 -> 4 -> 9 -> 10 -> 12 -> NULL
Input:
0
3
5 6 7
Output:
5 -> 6 -> 7 -> NULL
Time O(n + m), space O(1). This is the merge step of merge sort on linked lists, which sorts a list in O(n log n) using the "first middle" trick to split it.
Practice questions (with solutions)
1. Your turn: where does the cycle start? Solved above, with the proof.
2. Is a linked list a palindrome? (1 2 3 2 1 reads the same both ways.) Do it in O(n) time and O(1) extra space.
Solution
Find the end of the first half with slow and fast (fast starts at head->next, so slow stops at the first middle), reverse the second half, compare the two halves, then reverse the second half back so the caller's list is unchanged.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* readList() { // n, then n numbers
int n;
cin >> n;
Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Node* node = new Node{x, nullptr};
if (head == nullptr) head = node;
else tail->next = node;
tail = node;
}
return head;
}
void print(Node* head) {
for (Node* cur = head; cur != nullptr; cur = cur->next)
cout << cur->data << " -> ";
cout << "NULL\n";
}
void freeList(Node*& head) {
while (head != nullptr) {
Node* nxt = head->next;
delete head;
head = nxt;
}
}
Node* reverse(Node* head) {
Node* prev = nullptr;
while (head != nullptr) {
Node* nxt = head->next;
head->next = prev;
prev = head;
head = nxt;
}
return prev;
}
bool isPalindrome(Node* head) {
if (head == nullptr) return true;
Node* slow = head; // find the end of the first half
Node* fast = head->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
Node* second = reverse(slow->next); // reverse the second half
bool ok = true;
for (Node *a = head, *b = second; b != nullptr; a = a->next, b = b->next)
if (a->data != b->data) { ok = false; break; }
slow->next = reverse(second); // put the list back as it was
return ok;
}
int main() {
Node* head = readList();
cout << (isPalindrome(head) ? "palindrome\n" : "not a palindrome\n");
print(head);
freeList(head);
return 0;
}
Input:
5
1 2 3 2 1
Output:
palindrome
1 -> 2 -> 3 -> 2 -> 1 -> NULL
Input:
4
1 2 2 3
Output:
not a palindrome
1 -> 2 -> 2 -> 3 -> NULL
Input:
4
1 2 2 1
Output:
palindrome
1 -> 2 -> 2 -> 1 -> NULL
3. Delete the middle node in one pass (the second middle for an even count).
Solution
To unlink a node you need the node before it, so start fast two steps ahead: slow then stops just before the middle. One node: the list becomes empty.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* readList() { // n, then n numbers
int n;
cin >> n;
Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Node* node = new Node{x, nullptr};
if (head == nullptr) head = node;
else tail->next = node;
tail = node;
}
return head;
}
void print(Node* head) {
for (Node* cur = head; cur != nullptr; cur = cur->next)
cout << cur->data << " -> ";
cout << "NULL\n";
}
void freeList(Node*& head) {
while (head != nullptr) {
Node* nxt = head->next;
delete head;
head = nxt;
}
}
void deleteMiddle(Node*& head) {
if (head == nullptr) return;
if (head->next == nullptr) { // one box: it IS the middle
delete head;
head = nullptr;
return;
}
Node* slow = head; // stops just BEFORE the middle
Node* fast = head->next->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
Node* gone = slow->next; // the (second) middle
slow->next = gone->next;
delete gone;
}
int main() {
Node* head = readList();
deleteMiddle(head);
print(head);
freeList(head);
return 0;
}
Input:
5
10 20 30 40 50
Output:
10 -> 20 -> 40 -> 50 -> NULL
Input:
6
10 20 30 40 50 60
Output:
10 -> 20 -> 30 -> 50 -> 60 -> NULL
Input:
1
10
Output:
NULL
4. Reverse only the first k nodes.
Solution
Run the reverse loop k times. Afterwards cur is the (k+1)-th node and the old head is now the k-th: link it to cur. If k is bigger than the list, the whole list is reversed.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* readList() { // n, then n numbers
int n;
cin >> n;
Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Node* node = new Node{x, nullptr};
if (head == nullptr) head = node;
else tail->next = node;
tail = node;
}
return head;
}
void print(Node* head) {
for (Node* cur = head; cur != nullptr; cur = cur->next)
cout << cur->data << " -> ";
cout << "NULL\n";
}
void freeList(Node*& head) {
while (head != nullptr) {
Node* nxt = head->next;
delete head;
head = nxt;
}
}
Node* reverseFirstK(Node* head, int k) {
Node* prev = nullptr;
Node* cur = head;
for (int i = 0; i < k && cur != nullptr; i++) {
Node* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
if (head != nullptr) head->next = cur; // the old head is now k-th: link the rest
return prev; // the new head
}
int main() {
Node* head = readList();
int k;
cin >> k;
head = reverseFirstK(head, k);
print(head);
freeList(head);
return 0;
}
Input: 1 2 3 4 5 6, k = 3:
3 -> 2 -> 1 -> 4 -> 5 -> 6 -> NULL
Input: 1 2 3, k = 10:
3 -> 2 -> 1 -> NULL
Quick quiz
1. Where does slow stop? (the episode quiz: fast starts one node ahead)
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* readList() { // n, then n numbers
int n;
cin >> n;
Node* head = nullptr;
Node* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
Node* node = new Node{x, nullptr};
if (head == nullptr) head = node;
else tail->next = node;
tail = node;
}
return head;
}
void print(Node* head) {
for (Node* cur = head; cur != nullptr; cur = cur->next)
cout << cur->data << " -> ";
cout << "NULL\n";
}
void freeList(Node*& head) {
while (head != nullptr) {
Node* nxt = head->next;
delete head;
head = nxt;
}
}
int main() {
Node* head = readList();
Node* slow = head;
Node* fast = head->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
cout << slow->data << "\n";
freeList(head);
return 0;
}
Input 4 / 1 2 3 4. (A) 1 (B) 2 (C) 3 (D) 4
Answer
(B) 2. fast goes 2 → 4, slow goes 1 → 2; 4's next is nullptr, so the loop stops. Starting fast one node ahead gives the first middle.
Input:
4
1 2 3 4
Output:
2
2. The fixed Q2 program with input 2 / 10 20 prints?
Answer
The second middle:
Input:
2
10 20
Output:
middle: 20
3. On a list with a cycle of length L that starts a steps from the head, how many steps can Floyd's loop take at most before slow == fast?
Answer
slow needs a steps to enter the cycle, and then fast catches it in fewer than L more steps (the gap shrinks by 1 each step). So fewer than a + L ≤ n steps: O(n).
4. Why does Floyd's check compare slow == fast and not slow->data == fast->data?
Answer
Different nodes can hold the same value: in 1 -> 2 -> 1 -> 2 -> NULL, comparing values would claim a cycle. Comparing the pointers asks "is this the same node?".
Interview questions
- Reverse a linked list iteratively. Three pointers
prev,cur,nxt: remember, flip, step; returnprev. O(n) time, O(1) space. - Why is the recursive reverse worse? O(n) call-stack space; a long list can overflow the stack.
- Find the middle in one pass. Slow 1 step, fast 2 steps,
while (fast && fast->next); slow is the (second) middle. - How do you get the first middle instead? Start
fastathead->next. - Why
fast != nullptr && fast->next != nullptr, in that order? For an even countfastbecomesnullptr;&&short-circuits, sofast->nextis only read whenfastexists. - How do you detect a cycle in O(1) space? Floyd's tortoise and hare: they meet if and only if there is a cycle.
- Why can't fast jump over slow? Inside the cycle the gap shrinks by exactly 1 per step, so it hits 0.
- How do you find where the cycle starts? After they meet, move one pointer to the head and step both by 1; they meet at the start (a = kL − b).
- How do you find the length of the cycle? After they meet, keep one pointer still and walk the other until it comes back, counting steps.
- How do you remove the cycle? Find the start, walk to the node whose
nextis the start, and set thatnexttonullptr. - Check if a list is a palindrome in O(1) space. Find the middle, reverse the second half, compare, reverse it back.
- What is a dummy node and why use one? A fake first node so that inserting before the real head needs no special case; return
dummy.next.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Reverse in place | Reverse by changing arrows only, without new nodes | 40 -> 30 -> 20 -> 10 |
prev / cur / nxt |
The node before, the current node, the saved next node | remember, flip, step |
| Two-pointer technique | Two pointers moving through the data at different speeds or from different ends | slow and fast |
| Slow and fast pointers | One moves 1 node per step, the other 2 | slow = slow->next; fast = fast->next->next; |
| Middle (first / second) | For an even count, the two centre nodes | 10 20 30 40: 20 / 30 |
| One pass | Walking the data only once | the slow/fast middle |
| Short-circuit evaluation | && stops at the first false |
fast != nullptr && fast->next != nullptr |
| Cycle (loop) | A node's next points back to an earlier node, so walking never ends |
50 → 30 |
| Rho shape (6 shape) | A list with a tail leading into a cycle | pos = 2 |
| Floyd's algorithm | Cycle detection with slow and fast pointers | if (slow == fast) return true; |
| Tortoise and hare | Another name for Floyd's algorithm | slow = tortoise, fast = hare |
| Cycle start | The first node of the loop | 30 for pos = 2 |
unordered_set |
A hash set: fast "have I seen it?" checks | unordered_set<Node*> seen; |
| Dummy node | A fake first node that removes head special cases | Node dummy{0, nullptr}; |
| Merge | Combine two sorted lists into one sorted list | 1 2 3 4 9 10 12 |
| Palindrome | Reads the same forwards and backwards | 1 2 3 2 1 |
| Call stack | Memory holding one frame per active function call | recursion depth n |
| Stack overflow | The call stack runs out of space | recursive reverse of millions of nodes |
| Segmentation fault | The program touched memory it does not own | nullptr->next |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | waiting to see head again |
| O(1) extra space | Memory use that does not grow with n | three pointers |
| Memory leak | Memory made with new and never deleted |
20, 30, 40 after the broken reverse |
Summary
- Reverse: remember
nxt, flipcur->next = prev, stepprev = cur; cur = nxt. Returnprev. O(n) time, O(1) space. - Middle: slow 1 step, fast 2 steps,
while (fast != nullptr && fast->next != nullptr). Second middle for an even count; start fast athead->nextfor the first. - Cycle: Floyd's algorithm.
slow == fast→ cycle;fastreachesnullptr→ no cycle. Reset one pointer to the head and step both by 1 to find where the cycle starts. - Never free a list with a cycle with a plain
freeList: free each node exactly once.
Next episode: Class design questions: a Fraction class with operator overloading, a template Stack<T>, and the shallow copy double free (the rule of three).