Quartz 4

4.0 Linked-Lists

2 min read

Linked Lists

Fundamental pointer-based structure. Core to recursion, in-place manipulation, and memory management patterns.

1.0 Basics and Traversal

  1. Single and Doubly Linked Lists
  2. Iterative vs Recursive Traversal
  3. Handling nulls and one-node cases

2.0 Two Pointers (Fast & Slow)

  1. Cycle detection (Floyd’s algorithm)
  2. Finding midpoint
  3. Detecting palindrome in-place

3.0 Reversal Techniques

  1. Full reversal (iterative and recursive)
  2. Partial reversal between m and n
  3. Reverse in groups of K nodes

4.0 Merge and Sort Operations

  1. Merge two sorted lists
  2. Merge K sorted lists (using heap)
  3. Sort linked list (merge sort)

5.0 Deletion and Manipulation

  1. Delete N-th node from end
  2. Delete given node (without head)
  3. Remove duplicates

6.0 Cloning and Deep Copies

  1. Clone list with random pointer
  2. HashMap-based vs O(1) interleaving method

7.0 Advanced Structural Problems

  1. Intersection of two lists
  2. Detect start of cycle
  3. Flatten multi-level linked list
  4. Reorder list (alternate merge)

8.0 Circular and Doubly Linked Lists (Special Cases)

  1. Circular loop detection and breaking
  2. DLL insert/delete patterns
  3. Applications in LRU/Deque

9.0 Design Applications

  1. LRU Cache (DLL + HashMap)
  2. Browser history (bi-directional navigation)
  3. Music/Carousel queue rotation

10.0 Special Mentions

  1. Floyd’s Cycle Detection
  2. Recursive reversal variations
  3. In-place manipulation with pointer gymnastics
  4. Dummy node patterns

11.0 Math-Based Linked List Operations

  1. Add two numbers (forward and reverse order)
  2. Subtract two numbers (handle borrow cases)
  3. Multiply two numbers (simulating digit-by-digit)
  4. Convert linked list to number and back
  5. Edge handling: carry, leading zeros, unequal lengths

Graph View

Backlinks