Linked List Manipulation

1. Reverse Linked List Iterative Recursive

Approach	Technique	Time	Space
Iterative	Three pointers: prev, curr, next. Reverse links one by one	`O(n)`	`O(1)`
Recursive	Reverse rest of list, then fix current node's next pointer	`O(n)`	`O(n)` stack
Tail Recursive	Pass accumulator (reversed part) through recursive calls	`O(n)`	`O(n)` stack
Reverse Sublist	Reverse portion [m, n], reconnect with unchanged parts	`O(n)`	`O(1)`

Example: Iterative reversal

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverseListIterative(head) {
    let prev = null;
    let curr = head;
    
    while (curr !== null) {
        const next = curr.next; // Save next
        curr.next = prev;       // Reverse link
        prev = curr;            // Move prev forward
        curr = next;            // Move curr forward
    }
    
    return prev; // New head
}

// Example: 1->2->3->4->5
// Result:  5->4->3->2->1

// Create list
let head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

head = reverseListIterative(head);
// Now: 3->2->1

Example: Recursive reversal

function reverseListRecursive(head) {
    // Base case
    if (head === null || head.next === null) {
        return head;
    }
    
    // Reverse rest of list
    const newHead = reverseListRecursive(head.next);
    
    // Fix current node
    head.next.next = head; // Point next node back to current
    head.next = null;      // Remove forward link
    
    return newHead;
}

// Tail recursive version
function reverseListTailRecursive(head, prev = null) {
    if (head === null) {
        return prev;
    }
    
    const next = head.next;
    head.next = prev;
    
    return reverseListTailRecursive(next, head);
}

// Both produce same result: 3->2->1

Example: Reverse sublist [m, n]

function reverseBetween(head, left, right) {
    if (left === right) return head;
    
    const dummy = new ListNode(0, head);
    let prev = dummy;
    
    // Move to node before left position
    for (let i = 1; i < left; i++) {
        prev = prev.next;
    }
    
    // Reverse the sublist
    let curr = prev.next;
    for (let i = 0; i < right - left; i++) {
        const next = curr.next;
        curr.next = next.next;
        next.next = prev.next;
        prev.next = next;
    }
    
    return dummy.next;
}

// Example: 1->2->3->4->5, left=2, right=4
// Result:  1->4->3->2->5

2. Merge Two Sorted Lists

Approach	Method	Time	Space
Iterative	Compare heads, append smaller, advance pointer	`O(n + m)`	`O(1)`
Recursive	Choose smaller head, merge rest recursively	`O(n + m)`	`O(n + m)` stack
Dummy Head	Use dummy node to simplify edge cases	`O(n + m)`	`O(1)`
In-place	Rearrange nodes without creating new nodes	`O(n + m)`	`O(1)`

Example: Merge iterative with dummy

function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0);
    let curr = dummy;
    
    while (l1 !== null && l2 !== null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    // Append remaining nodes
    curr.next = l1 !== null ? l1 : l2;
    
    return dummy.next;
}

// Example:
// l1: 1->3->5
// l2: 2->4->6
// Result: 1->2->3->4->5->6

Example: Merge recursive

function mergeTwoListsRecursive(l1, l2) {
    // Base cases
    if (l1 === null) return l2;
    if (l2 === null) return l1;
    
    // Choose smaller head
    if (l1.val <= l2.val) {
        l1.next = mergeTwoListsRecursive(
            l1.next, 
            l2
        );
        return l1;
    } else {
        l2.next = mergeTwoListsRecursive(
            l1, 
            l2.next
        );
        return l2;
    }
}

// Elegant recursive solution
// Each call handles one node

3. Remove Nth Node From End

Technique	Strategy	Passes	Edge Cases
Two Pass	Count length, then remove (length - n)th node	`2`	Handle when n = length (remove head)
One Pass (Two Pointers)	Fast pointer n steps ahead, move both until fast reaches end	`1`	Use dummy head for edge cases
Dummy Node Trick	Add dummy before head to handle head removal uniformly	`1`	Simplifies all edge cases
Recursive	Return count from end, remove when count = n	`1`	Uses call stack space

Example: Remove Nth from end (one pass)

function removeNthFromEnd(head, n) {
    const dummy = new ListNode(0, head);
    let fast = dummy;
    let slow = dummy;
    
    // Move fast n+1 steps ahead
    for (let i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // Move both until fast reaches end
    while (fast !== null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // Remove nth node
    slow.next = slow.next.next;
    
    return dummy.next;
}

// Example: 1->2->3->4->5, n=2
// Remove 4 (2nd from end)
// Result: 1->2->3->5

// Key insight: Gap of n between fast and slow
// When fast reaches end, slow is at node before target

Note: The dummy node pattern is crucial for linked list problems. It eliminates special cases for removing the head node and simplifies code significantly.

4. Reorder List Pattern

Step	Action	Pattern Used	Purpose
1. Find Middle	Use slow-fast pointers to find middle node	Fast & slow pointers	Split list into two halves
2. Reverse Second Half	Reverse the second half of list	Reverse linked list	Prepare for interleaving
3. Merge Alternately	Merge first and reversed second half	Two pointers merge	Achieve L0→Ln→L1→Ln-1 pattern
Edge Cases	Handle odd/even length, single node, empty list	Boundary checks	Ensure correctness

Example: Reorder list (L0→Ln→L1→Ln-1...)

function reorderList(head) {
    if (!head || !head.next) return;
    
    // Step 1: Find middle
    let slow = head, fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // Step 2: Reverse second half
    let second = slow.next;
    slow.next = null; // Split list
    
    let prev = null;
    while (second) {
        const next = second.next;
        second.next = prev;
        prev = second;
        second = next;
    }
    second = prev; // Head of reversed second half
    
    // Step 3: Merge alternately
    let first = head;
    while (second) {
        const tmp1 = first.next;
        const tmp2 = second.next;
        
        first.next = second;
        second.next = tmp1;
        
        first = tmp1;
        second = tmp2;
    }
}

// Example: 1->2->3->4->5
// Result:  1->5->2->4->3

5. Copy List with Random Pointer

Approach	Strategy	Time	Space
Hash Map	Map old nodes to new nodes, then set next/random pointers	`O(n)`	`O(n)`
Interleaving	Insert copied nodes after originals, set random, then separate	`O(n)`	`O(1)`
Two Pass Hash	First pass: create nodes, second pass: set pointers	`O(n)`	`O(n)`
Recursive	Clone using recursion with memoization map	`O(n)`	`O(n)`

Example: Copy using hash map

class RandomListNode {
    constructor(val, next = null, random = null) {
        this.val = val;
        this.next = next;
        this.random = random;
    }
}

function copyRandomList(head) {
    if (!head) return null;
    
    const map = new Map();
    
    // First pass: create all nodes
    let curr = head;
    while (curr) {
        map.set(curr, new RandomListNode(curr.val));
        curr = curr.next;
    }
    
    // Second pass: set next and random pointers
    curr = head;
    while (curr) {
        const newNode = map.get(curr);
        newNode.next = map.get(curr.next) || null;
        newNode.random = map.get(curr.random) || null;
        curr = curr.next;
    }
    
    return map.get(head);
}

Example: Copy with O(1) space (interleaving)

function copyRandomListO1(head) {
    if (!head) return null;
    
    // Step 1: Create interleaved list
    // A->B->C becomes A->A'->B->B'->C->C'
    let curr = head;
    while (curr) {
        const copy = new RandomListNode(curr.val);
        copy.next = curr.next;
        curr.next = copy;
        curr = copy.next;
    }
    
    // Step 2: Set random pointers
    curr = head;
    while (curr) {
        if (curr.random) {
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }
    
    // Step 3: Separate lists
    const newHead = head.next;
    curr = head;
    while (curr) {
        const copy = curr.next;
        curr.next = copy.next;
        copy.next = copy.next ? copy.next.next : null;
        curr = curr.next;
    }
    
    return newHead;
}

6. Flatten Multilevel List

Structure Type	Approach	Traversal	Complexity
Doubly Linked with Child	DFS: process child before next, reconnect pointers	Depth-first	`O(n)` time, `O(n)` space
Iterative Stack	Use stack to save next pointer when child exists	Explicit stack	`O(n)` time, `O(n)` space
Recursive	Flatten child, attach to current, continue with next	Recursive DFS	`O(n)` time, `O(d)` depth
Two Pointer	Current pointer + find tail of child list	Iterative	`O(n)` time, `O(1)` space

Example: Flatten doubly linked list with child pointer

class DoublyListNode {
    constructor(val, prev = null, next = null, child = null) {
        this.val = val;
        this.prev = prev;
        this.next = next;
        this.child = child;
    }
}

function flatten(head) {
    if (!head) return head;
    
    const stack = [];
    let curr = head;
    
    while (curr) {
        // If child exists, process it first
        if (curr.child) {
            // Save next for later
            if (curr.next) {
                stack.push(curr.next);
            }
            
            // Connect child
            curr.next = curr.child;
            curr.child.prev = curr;
            curr.child = null;
        }
        
        // If no next but stack has nodes, pop from stack
        if (!curr.next && stack.length > 0) {
            const next = stack.pop();
            curr.next = next;
            next.prev = curr;
        }
        
        curr = curr.next;
    }
    
    return head;
}

// Example:
// 1->2->3->4
//    |
//    7->8
//    |
//    11->12
//
// Flattened: 1->2->7->11->12->8->3->4

Example: Flatten recursive approach

function flattenRecursive(head) {
    if (!head) return head;
    
    // Helper returns tail of flattened list
    function flattenDFS(node) {
        let curr = node;
        let tail = node;
        
        while (curr) {
            const next = curr.next;
            
            if (curr.child) {
                // Flatten child
                const childTail = flattenDFS(curr.child);
                
                // Connect child
                curr.next = curr.child;
                curr.child.prev = curr;
                curr.child = null;
                
                // Connect tail of child to next
                if (next) {
                    childTail.next = next;
                    next.prev = childTail;
                }
                
                tail = childTail;
            }
            
            if (next) {
                tail = next;
            }
            
            curr = next;
        }
        
        return tail;
    }
    
    flattenDFS(head);
    return head;
}

// Cleaner recursive solution
// Processes entire subtree before moving to next

Note: When flattening multilevel lists:

Always process child before next for depth-first traversal
Use stack to save next pointer when diving into child
Set child pointer to null after flattening to avoid cycles
Update both prev and next pointers for doubly linked lists

Summary: Linked List Manipulation Patterns

Reversal Pattern: Three pointers (prev, curr, next) for iterative O(1) space; recursive uses O(n) stack but is elegant
Dummy Head Trick: Add dummy node before head to handle edge cases uniformly, especially for removing head or empty lists
Two Pointers: Fast-slow for finding middle, gap of n for nth from end, merge pattern for sorted lists
Reverse Sublist: Find boundaries, reverse middle portion, reconnect - all in one pass
Merge Sorted: Compare heads, append smaller, advance pointer - works iteratively O(1) or recursively O(n) space
Remove Nth from End: One-pass with two pointers: fast moves n+1 ahead, then both move until fast reaches end
Reorder List: Three-step pattern: find middle, reverse second half, merge alternately
Copy with Random: Hash map O(n) space or interleaving O(1) space - both O(n) time with two passes
Flatten Multilevel: DFS pattern - process child before next, use stack for iterative or recursion for elegant solution
Common Edge Cases: Empty list, single node, removing head, odd/even length, cycles
Space Optimization: Prefer iterative over recursive for O(1) space when possible
Pointer Management: Always update both prev and next for doubly linked lists; set child/random to null after processing

Related Cheatsheets

Datastructures-algorithms