SyntaxPilot
Courses/C++ Coding Questions/Lesson 23
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 23 of 30

Linked list questions II

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

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

  1. Remember the next node: Node* nxt = cur->next;
  2. Flip the arrow: cur->next = prev;
  3. 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

  1. Reverse a linked list iteratively. Three pointers prev, cur, nxt: remember, flip, step; return prev. O(n) time, O(1) space.
  2. Why is the recursive reverse worse? O(n) call-stack space; a long list can overflow the stack.
  3. Find the middle in one pass. Slow 1 step, fast 2 steps, while (fast && fast->next); slow is the (second) middle.
  4. How do you get the first middle instead? Start fast at head->next.
  5. Why fast != nullptr && fast->next != nullptr, in that order? For an even count fast becomes nullptr; && short-circuits, so fast->next is only read when fast exists.
  6. 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.
  7. Why can't fast jump over slow? Inside the cycle the gap shrinks by exactly 1 per step, so it hits 0.
  8. 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).
  9. 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.
  10. How do you remove the cycle? Find the start, walk to the node whose next is the start, and set that next to nullptr.
  11. Check if a list is a palindrome in O(1) space. Find the middle, reverse the second half, compare, reverse it back.
  12. 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, flip cur->next = prev, step prev = cur; cur = nxt. Return prev. 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 at head->next for the first.
  • Cycle: Floyd's algorithm. slow == fast → cycle; fast reaches nullptr → 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).