Linked List Patterns

LinkedLists have unique properties: sequential nodes, pointers, and often unknown length. Recognizing patterns helps solve problems efficiently without reinventing solutions each time. This file lists commonly used LinkedList patterns, the typical problems, keywords to detect them, why they work, and their scope.

Once read thoroughly, the input structures, keywords, and triggers should stay in your mind for instant pattern recognition.

---

Pattern Table (Simplified & Prioritized, 4 Columns)

Pattern	Typical Question Types	Keywords / Detection Cues	Why Use / Notes
Fast & Slow Pointers	Detect cycle, Find middle	slow, fast, meet, middle	Two pointers moving at different speeds; detect cycles or middle efficiently.
Reverse LinkedList	Reverse entire list, Sublist reversal	reverse, next, prev	Iterative or recursive reversal; adjust next pointers carefully.
Merge Two Lists	Merge sorted lists, Add two numbers	merge, sorted, combine	Classic two-pointer approach; traverse both lists simultaneously.
Remove N-th Node	Delete node from end/start	remove, nth, delete	Maintain previous pointer; handle head/tail edge cases.
LinkedList Cycle Check	Detect loop	cycle, loop, fast/slow	Use fast & slow pointers or hashmap to detect loops.
Flatten / Reorder List (Bonus)	Flatten multilevel list, Reorder	flatten, reorder	Advanced manipulations; recursive or iterative traversal; change node connections.
Two Pointers (Universal)	Palindrome check, Pair sum	left/right, start/end	Shrink/grow pointers; works on LinkedList, Arrays, or Strings.
Hashing (Universal)	Detect duplicates, Find cycle	hashmap, visited	Store node references; universal detection of cycles/duplicates.

---

Mini Notes / Tips

### Tips

- Always start by understanding the **linked list structure**: singly, doubly, or multilevel.
- Look for **keywords**: slow/fast, middle, next/prev, merge, remove, cycle, flatten, left/right, visited.
- Fast & slow pointers: ideal for detecting loops, middle node, or cycle length.
- Reversing: always update next pointers carefully; edge cases at head and tail.
- Merging: two-pointer traversal simplifies combining sorted lists or numbers.
- Removing nth node: maintain previous pointer and handle head/tail properly.
- Flatten/Reorder: rare but often appear in multilevel or reordering interview problems.
- Two pointers & Hashing: universal patterns; reusable across linked lists, arrays, and even strings or graphs.

---

LinkedList Patterns – Detection & Usage Guide

---

1. Fast & Slow Pointers – Common (LinkedList / Arrays)

When to use / Detection cues:

• Input structure: Singly linked list, possibly with a cycle.
• Question keywords: slow, fast, meet, middle.
• Problem hints: Find middle node, detect cycles, determine loop length.
• Why it works: Two pointers moving at different speeds converge at predictable points (cycle detection or middle node).

Typical questions:

• Detect loop in a linked list
• Find middle node
• Find cycle length

Mental trigger: “Two speeds (fast/slow)” → Fast & Slow Pointers.

---

2. Reverse LinkedList – Common (LinkedList only)

When to use / Detection cues:

• Input structure: Singly or doubly linked list.
• Question keywords: reverse, next, prev.
• Problem hints: Reverse entire list or a portion (sublist); often done in-place.
• Why it works: Iteratively or recursively update next pointers to reverse connections; careful with head/tail.

Typical questions:

• Reverse entire linked list
• Reverse sublist from position m to n
• Reverse K-group nodes

Mental trigger: “Reverse next pointers” → Reverse LinkedList.

---

3. Merge Two Lists – Common (LinkedList only)

When to use / Detection cues:

• Input structure: Two sorted singly linked lists.
• Question keywords: merge, sorted, combine.
• Problem hints: Merge efficiently in one pass using two pointers.
• Why it works: Maintain two pointers; pick smaller node at each step and connect to merged list.

Typical questions:

• Merge two sorted linked lists
• Add two numbers represented by linked lists

Mental trigger: “Combine sorted lists” → Merge Two Lists.

---

4. Remove N-th Node – Common (LinkedList only)

When to use / Detection cues:

• Input structure: Singly linked list.
• Question keywords: remove, nth, delete.
• Problem hints: Delete node counting from head or tail; often use dummy node to simplify edge cases.
• Why it works: Maintain previous pointer and skip target node; handles head and tail elegantly.

Typical questions:

• Remove N-th node from end
• Delete node at given position

Mental trigger: “Delete nth node” → Remove N-th Node.

---

5. LinkedList Cycle Check – Common (LinkedList only)

When to use / Detection cues:

• Input structure: Linked list with possible cycle.
• Question keywords: cycle, loop, fast/slow.
• Problem hints: Detect loop using Floyd’s cycle detection or hash set.
• Why it works: Fast and slow pointers meet in cycle; hash set tracks visited nodes.

Typical questions:

• Detect cycle in linked list
• Find start of loop

Mental trigger: “Cycle detection” → LinkedList Cycle Check.

---

6. Flatten / Reorder List – Rare / Bonus (LinkedList only)

When to use / Detection cues:

• Input structure: Multilevel linked list or list requiring reordering.
• Question keywords: flatten, reorder.
• Problem hints: Recursively or iteratively connect child/next nodes; reorder by pattern (L0 → Ln → L1 → Ln-1…).
• Why it works: Modify node connections carefully; advanced traversal.

Typical questions:

• Flatten multilevel linked list
• Reorder list in L0→Ln→L1→Ln-1 pattern

Mental trigger: “Flatten/reorder” → Flatten / Reorder List.

---

7. Two Pointers (Universal) – Common (LinkedList / Arrays / Strings)

When to use / Detection cues:

• Input structure: Linked list or array/string.
• Question keywords: left/right, start/end.
• Problem hints: Shrink/grow pointers toward each other; detect palindrome, pair sum, or partition.
• Why it works: Generalized two-pointer approach; works for LinkedList, Arrays, Strings.

Typical questions:

• Check palindrome linked list
• Pair sum = target in sorted linked list

Mental trigger: “Left/right pointers moving inward” → Two Pointers.

---

8. Hashing (Universal) – Common (LinkedList / Arrays / Graphs)

When to use / Detection cues:

• Input structure: Linked list, array, or graph.
• Question keywords: hashmap, visited.
• Problem hints: Detect duplicates, loops, or repeated patterns.
• Why it works: Store node references in hash set; check for repeated visits in O(1).

Typical questions:

• Detect cycle using hash set
• Find duplicate nodes
• Track visited nodes in graphs

Mental trigger: “Visited / hash” → Hashing.

---

Mini Notes / Tips

### Tips

- Understand **linked list properties**: singly, doubly, multilevel.
- Identify **keywords**: fast/slow, middle, reverse, merge, nth, cycle, flatten, left/right, visited.
- Fast & Slow Pointers: detect cycle or middle node efficiently.
- Reversing: careful pointer updates; edge cases for head/tail.
- Merging: traverse both lists simultaneously.
- Remove N-th node: use dummy node to simplify deletion logic.
- Flatten/Reorder: rare but important; requires careful node connections.
- Two Pointers & Hashing: universal patterns; reusable across structures.
- Mental trigger: always map **input → keyword → local choice → global solution**.