Learn DSA Part 5: Linked List - Reversal, Fast and Slow Pointers and Interview Problems

Linked lists are rarely the fastest choice in real programs, yet they are an interview favourite, because they test whether you can manipulate pointers carefully without losing nodes. A handful of techniques (dummy heads, in-place reversal and slow/fast pointers) solve almost every linked list question you will be asked.

This is Part 5 of the Learn DSA series. We cover how linked lists work, how they compare with arrays, and the core techniques with C++ and Java code.

1. How a linked list works

A linked list is a chain of nodes. Each node stores a value and a pointer (reference) to the next node; the last node points to null. Unlike an array, the nodes are scattered in memory, so you cannot jump to the i-th element directly; you must walk from the head.

• Singly linked: each node has next only.
• Doubly linked: each node also has prev, so you can delete a node in O(1) when you already hold a pointer to it.
• Circular: the last node points back to the first.

2. Technique 1: in-place reversal

Reversing a list is the single most important linked list skill; it appears on its own and inside harder problems such as Palindrome Linked List, Reorder List and Reverse Nodes in k-Group. Walk the list with three pointers and flip each next link to point backwards.

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

// Reverse a singly linked list in place. O(n) time, O(1) space
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;  // save the rest of the list
        curr->next = prev;            // flip the link
        prev = curr;
        curr = next;
    }
    return prev;                      // new head
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int v) { val = v; }
}

// Reverse a singly linked list in place. O(n) time, O(1) space
static ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;    // save the rest of the list
        curr.next = prev;             // flip the link
        prev = curr;
        curr = next;
    }
    return prev;                      // new head
}

Always save curr.next before changing it; losing that reference is the classic bug that cuts the list in half. A recursive version also works but uses O(n) stack space, so the iterative version is preferred.

3. Technique 2: slow and fast pointers

Move slow one step and fast two steps at a time:

• Middle of the list: when fast reaches the end, slow is at the middle.
• Cycle detection (Floyd's algorithm): if there is a cycle, fast eventually laps slow and they meet. If fast reaches null, there is no cycle.
• Start of the cycle: after they meet, move one pointer back to the head and advance both one step at a time; they meet again exactly at the node where the cycle begins.
• N-th node from the end: move one pointer n steps ahead, then move both together until the leading pointer reaches the end.

// Floyd's cycle detection. O(n) time, O(1) space
bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

// Floyd's cycle detection. O(n) time, O(1) space
static boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

All of these run in O(n) time and O(1) extra space, which is why interviewers prefer them to the simpler "store visited nodes in a hash set" approach.

4. Technique 3: the dummy head and merging

Many bugs come from special-casing the head node. A dummy (sentinel) node placed before the real head removes those special cases: build the result after the dummy and return dummy.next at the end. Merging two sorted lists is the standard example.

// Merge two sorted lists using a dummy head. O(n + m) time
ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else                  { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;   // attach the leftover part
    return dummy.next;
}

// Merge two sorted lists using a dummy head. O(n + m) time
static ListNode mergeTwoLists(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;   // attach the leftover part
    return dummy.next;
}

The same idea removes elements by value, partitions a list around a value, and adds two numbers stored as linked lists. Merging k sorted lists uses this merge together with a min-heap (Part 10).

5. Putting techniques together

Medium and hard linked list problems are usually two of the techniques above combined:

• Palindrome Linked List: find the middle (slow/fast), reverse the second half, compare the halves, and optionally restore the list.
• Reorder List (L0, Ln, L1, Ln-1, ...): find the middle, reverse the second half, then merge the two halves alternately.
• Intersection of Two Lists: walk two pointers; when one reaches the end, restart it at the other list's head. They meet at the intersection after at most m + n steps.
• LRU Cache: a hash map from key to node plus a doubly linked list ordered by recent use gives O(1) get and put.

Practice problems

These are classic LeetCode-style problems, listed from easy to hard. Draw the pointers on paper for each one before coding.

1. Reverse Linked List (easy)
2. Merge Two Sorted Lists (easy)
3. Linked List Cycle (easy)
4. Middle of the Linked List (easy)
5. Palindrome Linked List (easy)
6. Intersection of Two Linked Lists (easy)
7. Remove Nth Node From End of List (medium)
8. Add Two Numbers (medium)
9. Linked List Cycle II (medium)
10. Reorder List (medium)
11. Copy List with Random Pointer (medium)
12. LRU Cache (medium)
13. Merge k Sorted Lists (hard)
14. Reverse Nodes in k-Group (hard)