C++ In Practice - Linked Lists Internals

Linked List Manipulation (C++11 Deep Dive)

Linked Lists are unique because they force you to manage raw pointers. While std::list (doubly linked) and std::forward_list (singly linked) exist, didactic problems usually define a custom struct ListNode.

The Didactic Data Structure (Raw Pointers)

This is the standard definition you will encounter:

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

System Level Note: In modern C++ production code, you would rarely use raw pointers like this due to memory leak risks. You would use std::unique_ptr<Node> for strict ownership. However, for algorithms (and LeetCode), raw pointers are the standard.

---

1. Reverse Linked List (Iterative)

Pattern: Pointer manipulation.

Complexity: Time O(N) | Space O(1).

Deep Dive: We need three pointers: prev, curr, and next. The order of operations is critical to avoid losing the reference to the rest of the list.

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    
    while (curr != nullptr) {
        ListNode* nextTemp = curr->next; // 1. Save next
        curr->next = prev;               // 2. Reverse link
        prev = curr;                     // 3. Advance prev
        curr = nextTemp;                 // 4. Advance curr
    }
    
    return prev; // Prev is the new head
}

---

2. Merge Two Sorted Lists (The Dummy Node)

Pattern: Merge Sort Step.

Complexity: Time O(N + M) | Space O(1).

C++11 Optimization: Stack Allocation Instead of new ListNode(0) for the dummy node (which requires manual delete to prevent leaks), allocate the dummy node on the stack. Use the address operator & to get its pointer.

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0); // Stack allocation (RAII)
    ListNode* tail = &dummy;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // Attach remaining part
    if (l1) tail->next = l1;
    else if (l2) tail->next = l2;

    return dummy.next;
}

---

3. Merge K Sorted Lists (Priority Queue)

Pattern: Min-Heap.

Complexity: Time O(N \log K) | Space O(K).

C++11 Details: We need a custom comparator for the priority_queue because ListNode* comparison compares memory addresses, not values.

#include <vector>
#include <queue>

struct CompareNode {
    // Min-Heap needs 'greater' logic
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    std::priority_queue<ListNode*, std::vector<ListNode*>, CompareNode> pq;

    // 1. Init Heap
    for (ListNode* l : lists) {
        if (l) pq.push(l);
    }

    ListNode dummy(0);
    ListNode* tail = &dummy;

    // 2. Process Heap
    while (!pq.empty()) {
        ListNode* smallest = pq.top();
        pq.pop();

        tail->next = smallest;
        tail = tail->next;

        if (smallest->next) {
            pq.push(smallest->next);
        }
    }

    return dummy.next;
}

---

4. Cycle Detection (Floyd’s Cycle Finding)

Pattern: Fast & Slow Pointers.

Complexity: Time O(N) | Space O(1).

bool hasCycle(ListNode *head) {
    if (!head) return false;
    ListNode *slow = head;
    ListNode *fast = head;

    while (fast && fast->next) {
        slow = slow->next;       // 1 step
        fast = fast->next->next; // 2 steps

        if (slow == fast) return true;
    }
    return false;
}

---

5. LRU Cache (The STL Powerhouse)

Problem: O(1) Get and Put.

Architecture: Hash Map + Doubly Linked List.

Complexity: Time O(1) | Space O(N).

C++11 Implementation Strategy: We use std::list (Doubly Linked List) and std::unordered_map. The map stores {key, iterator_to_list_node}. The list stores {key, value} pairs (we need the key in the list to delete from the map during eviction).

The Secret Weapon: std::list::splice splice moves an element from one position to another within a list (or between lists) in O(1) time by simply adjusting pointers. It does not copy or reallocate memory.

#include <list>
#include <unordered_map>
#include <utility> // for std::pair

class LRUCache {
private:
    int capacity;
    // List stores pairs of <Key, Value>
    // Front = Most Recently Used, Back = Least Recently Used
    std::list<std::pair<int, int>> lruList; 
    
    // Map: Key -> Iterator to the node in lruList
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache;

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1;

        // Move this node to the front of the list (Mark as MRU)
        // splice(position_to_move_to, source_list, iterator_to_move)
        lruList.splice(lruList.begin(), lruList, it->second);

        return it->second->second;
    }

    void put(int key, int value) {
        auto it = cache.find(key);
        
        if (it != cache.end()) {
            // Key exists: Update value and move to front
            it->second->second = value;
            lruList.splice(lruList.begin(), lruList, it->second);
        } else {
            // Key does not exist: Insert
            if (cache.size() == capacity) {
                // Evict LRU (Back of list)
                int keyToDelete = lruList.back().first;
                lruList.pop_back();   // Remove from list
                cache.erase(keyToDelete); // Remove from map
            }
            
            // Insert new pair at front
            lruList.push_front({key, value});
            cache[key] = lruList.begin();
        }
    }
};

ASCII Visualization of STL LRU:

[ Map ]
 Key 1 -> Iterator --+
 Key 2 -> Iterator --|--+
                     |  |
                     v  v
[ std::list (Doubly Linked) ]
[ MRU ] <-> [ {1, Val} ] <-> [ {2, Val} ] <-> [ LRU ]

---

6. Remove Nth Node From End

Pattern: Two Pointers (Delay).

Logic: Move fast pointer n steps ahead. Then move fast and slow together. When fast hits end, slow is at N from end.

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* slow = &dummy;
    ListNode* fast = &dummy;

    // 1. Move fast ahead by n + 1 steps
    // (+1 ensures slow stops at the node BEFORE the one to delete)
    for (int i = 0; i <= n; ++i) {
        fast = fast->next;
    }

    // 2. Move both
    while (fast != nullptr) {
        slow = slow->next;
        fast = fast->next;
    }

    // 3. Skip the node
    ListNode* toDelete = slow->next;
    slow->next = slow->next->next;
    
    // In C++, we must manually free memory if we own it.
    // In LeetCode, it's optional but good practice to mention.
    // delete toDelete; 

    return dummy.next;
}

Summary of Linked List Patterns

Pattern	C++ Tool/Technique	Complexity
Reverse	3-Pointer Swap	O(N)
Merge	Stack-based Dummy Node	O(N)
Merge K	priority_queue with comparator	O(N \log K)
Cycle	Floyd's (Fast/Slow)	O(N)
LRU Cache	std::list (Splice) + unordered_map	O(1)
Nth from End	Offset Pointers	O(N)