Skip to content
DSA linked lists 12 min read

Linked List Exercises: Answer Sheet & Worked Solutions

This is the answer sheet for the linked list exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and common pitfalls. All examples assume a singly linked node with data and next fields. Try the problems first — then check your work here.

Q1. Reverse a singly linked list

Idea: Walk once with three pointers — prev, cur, and a saved next — flipping each link to point backward. When cur runs off the end, prev is the new head.

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

Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        Node* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

Pitfall: Forgetting to save cur.next before overwriting it strands the rest of the list. The saved pointer is the whole reason you need three variables. See reversing a linked list for the recursive version.

Q2. Find the middle node

Idea: Two fast/slow pointers — slow moves one step, fast two. When fast falls off the end, slow is at the middle. Starting both at the head returns the second middle for even lengths.

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

Node* middle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Pitfall: Check fast before fast.next in the condition, or an even-length list dereferences null and crashes.

Q3. Detect a cycle

Idea: Floyd’s tortoise and hare. If a cycle exists, the fast pointer laps the slow one and they meet; if not, fast reaches null first.

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

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Pitfall: A hash set of visited nodes also works in O(n) time but costs O(n) space. The two-pointer method is the O(1)-space answer interviewers want.

Q4. Merge two sorted lists

Idea: Use a dummy head and a tail pointer. Repeatedly attach the smaller of the two front nodes and advance that list. When one list runs out, attach the other wholesale.

Complexity: O(m + n) time, O(1) space.

Node* mergeTwo(Node* a, Node* b) {
    Node dummy(0);
    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;
    return dummy.next;
}

Pitfall: Use <= (not <) when comparing to keep the merge stable for equal values, and don’t forget to attach the leftover tail — dropping it loses half the result.

Q5. Remove the Nth node from the end

Idea: Start a fast pointer from a dummy head and advance it n + 1 steps. Then move fast and slow together until fast is null — now slow sits just before the target, ready to unlink it. One pass.

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

Node* removeNthFromEnd(Node* head, int n) {
    Node dummy(0);
    dummy.next = head;
    Node* fast = &dummy;
    Node* slow = &dummy;
    for (int i = 0; i <= n; i++) fast = fast->next; // n+1 ahead
    while (fast != nullptr) { fast = fast->next; slow = slow->next; }
    Node* doomed = slow->next;
    slow->next = doomed->next;
    delete doomed;
    return dummy.next;
}

Pitfall: The dummy head is what makes removing the first node (when n equals the length) work without a special case. Advancing fast by n + 1, not n, is what leaves slow on the predecessor.

Q6. Palindrome linked list

Idea: Find the middle with fast/slow, reverse the second half, then walk both halves comparing values. O(1) space because we reuse the nodes instead of copying to an array.

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

bool isPalindrome(Node* head) {
    if (head == nullptr || head->next == nullptr) return true;
    // find middle
    Node* slow = head; Node* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next; fast = fast->next->next;
    }
    // reverse second half (after slow)
    Node* prev = nullptr; Node* cur = slow->next;
    while (cur != nullptr) {
        Node* nx = cur->next; cur->next = prev; prev = cur; cur = nx;
    }
    // compare
    Node* a = head; Node* b = prev;
    while (b != nullptr) {
        if (a->data != b->data) return false;
        a = a->next; b = b->next;
    }
    return true;
}

Pitfall: Comparing only until b (the reversed half) is null avoids the middle-node mismatch on odd lengths. If you must not mutate the input, reverse the second half back after comparing.

Q7. Detect the cycle’s start node

Idea: Run Floyd’s detection until the pointers collide. Then reset one pointer to the head and advance both one step at a time — they meet exactly at the cycle’s entry. This follows from the distance equation: the gap from the head to the entry equals the gap from the meeting point to the entry.

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

Node* detectCycleStart(Node* head) {
    Node* slow = head; Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            Node* p = head;
            while (p != slow) { p = p->next; slow = slow->next; }
            return p;
        }
    }
    return nullptr;
}

Pitfall: The reset-and-walk step only works after a genuine collision inside the loop — don’t start it from the initial head == head position. Return null when fast reaches the end so acyclic lists are handled.

That’s the full answer sheet. Back to the linked list exercises or continue to stacks.

Last updated June 25, 2026
Was this helpful?