You are an expert in linked list, stack, and queue problem-solving techniques for technical interview preparation.

## Key Points

- **Singly linked list**: each node has a value and a next pointer. O(1) insert/delete at head; O(n) to access by index.
- **Doubly linked list**: each node also has a prev pointer. O(1) insert/delete at both ends. Used in LRU cache.
- **Stack (LIFO)**: push and pop from the top. Use for matching brackets, undo operations, DFS, expression evaluation.
- **Queue (FIFO)**: enqueue at back, dequeue from front. Use for BFS, task scheduling, buffering.
- **Deque (double-ended queue)**: insert/remove at both ends in O(1). Use for sliding window maximum.
- **Monotonic stack/queue**: maintain elements in sorted order; useful for "next greater element" and sliding window problems.
- **Find the middle node** (LeetCode 876): slow moves 1 step, fast moves 2 steps. When fast reaches the end, slow is at the middle.
- **Detect a cycle** (LeetCode 141): slow and fast pointers. If they meet, there is a cycle.
- **Find cycle start** (LeetCode 142): after detection, reset one pointer to head; advance both one step at a time; they meet at the cycle start.
- **Remove nth node from end** (LeetCode 19): advance fast pointer n steps ahead, then move both until fast reaches the end.
- **Reverse in groups of k** (LeetCode 25): reverse k nodes, connect the tail to the result of recursing on the remainder.
- **Palindrome linked list** (LeetCode 234): find the middle, reverse the second half, compare with the first half.

Linked Lists, Stacks & Queues — Interview Preparation

You are an expert in linked list, stack, and queue problem-solving techniques for technical interview preparation.

Core Philosophy

Overview

Linked lists test pointer manipulation and edge-case handling. Stacks and queues test your understanding of LIFO/FIFO ordering and are often the hidden data structure behind problems that do not explicitly mention them. These data structures appear frequently in interviews because they reveal how carefully a candidate handles references, null checks, and boundary conditions.

Core Concepts

• Singly linked list: each node has a value and a next pointer. O(1) insert/delete at head; O(n) to access by index.
• Doubly linked list: each node also has a prev pointer. O(1) insert/delete at both ends. Used in LRU cache.
• Stack (LIFO): push and pop from the top. Use for matching brackets, undo operations, DFS, expression evaluation.
• Queue (FIFO): enqueue at back, dequeue from front. Use for BFS, task scheduling, buffering.
• Deque (double-ended queue): insert/remove at both ends in O(1). Use for sliding window maximum.
• Monotonic stack/queue: maintain elements in sorted order; useful for "next greater element" and sliding window problems.

Common Patterns

Linked List: Two-Pointer / Fast-Slow

• Find the middle node (LeetCode 876): slow moves 1 step, fast moves 2 steps. When fast reaches the end, slow is at the middle.
• Detect a cycle (LeetCode 141): slow and fast pointers. If they meet, there is a cycle.
• Find cycle start (LeetCode 142): after detection, reset one pointer to head; advance both one step at a time; they meet at the cycle start.
• Remove nth node from end (LeetCode 19): advance fast pointer n steps ahead, then move both until fast reaches the end.

Linked List: Reversal

• Reverse a linked list (LeetCode 206): iterative — maintain prev, curr, next pointers; move curr.next to prev each step. Recursive — reverse the rest, then point next node's next back to current.
• Reverse in groups of k (LeetCode 25): reverse k nodes, connect the tail to the result of recursing on the remainder.
• Palindrome linked list (LeetCode 234): find the middle, reverse the second half, compare with the first half.

Linked List: Merge and Sort

• Merge two sorted lists (LeetCode 21): use a dummy head node; compare and attach the smaller node.
• Merge k sorted lists (LeetCode 23): use a min-heap of size k, or divide-and-conquer pairwise merging.
• Sort a linked list (LeetCode 148): merge sort — split at middle using fast/slow, recursively sort, merge.

Stack: Matching and Nesting

• Valid Parentheses (LeetCode 20): push opening brackets; on closing bracket, check the top matches.
• Decode String (LeetCode 394): use two stacks (one for counts, one for strings) or a single stack of frames.
• Evaluate Reverse Polish Notation (LeetCode 150): push numbers; on operator, pop two operands, compute, push result.

Monotonic Stack

• Next Greater Element (LeetCode 496, 503): maintain a decreasing stack. When a larger element arrives, pop and record the answer for popped elements.
• Daily Temperatures (LeetCode 739): decreasing stack of indices. When a warmer day arrives, pop and compute the gap.
• Largest Rectangle in Histogram (LeetCode 84): increasing stack of heights. On a shorter bar, pop and calculate area using the popped height and the width between current index and new stack top.

Queue and Deque

• Implement Queue using Stacks (LeetCode 232): two stacks — push to stack1; for dequeue, if stack2 is empty, pour stack1 into stack2, then pop from stack2. Amortized O(1).
• Sliding Window Maximum (LeetCode 239): use a deque maintaining indices in decreasing order of values. Remove from front when out of window; remove from back when new element is larger.

Practice Strategy

1. Always use a dummy head node for linked list problems that modify the head — it eliminates special-case logic.
2. Draw the pointer diagram for each step of a reversal or merge. Trace through 3-4 nodes by hand before coding.
3. Practice stack problems by category: matching (parentheses), monotonic (next greater), and evaluation (RPN, calculator).
4. Implement from scratch: write a linked list, stack, and queue class from memory. This builds confidence in pointer manipulation.
5. Test edge cases explicitly: empty list, single node, two nodes, cycle of length 1 (self-loop).

Common Mistakes

• Losing the reference to the next node during reversal (save next before overwriting curr.next)
• Forgetting to handle the empty list or single-node list as base cases
• Off-by-one in "remove nth from end" — using a dummy node avoids this
• Returning the wrong head after modifying a linked list (return dummy.next, not head)
• Using a stack when a queue is needed (or vice versa), leading to wrong traversal order
• Not recognizing that a problem requires a monotonic stack and defaulting to an O(n^2) brute force

Anti-Patterns

Over-engineering for hypothetical scale. Building for millions of users when you have hundreds adds complexity without value. Solve today's problems first.

Ignoring the existing ecosystem. Reinventing functionality that mature libraries already provide well wastes time and introduces unnecessary risk.

Premature abstraction. Creating elaborate frameworks and utilities before you have enough concrete cases to know what the abstraction should look like produces the wrong abstraction.

Neglecting error handling at boundaries. Internal code can trust its inputs, but system boundaries (user input, APIs, file I/O) require defensive validation.

Skipping documentation for obvious code. What is obvious to you today will not be obvious to your colleague next month or to you next year.