DSA Patterns: Linked Lists

📌 TL;DR

This blog is a deep dive into the most important patterns and templates used in Linked List problems — the kind that show up over and over again in coding interviews.

You’ll walk away with:

• 📦 7 essential Linked List patterns, each tied to a real Leetcode problem
• 🧠 Clean, reusable Java templates for each pattern
• 🧪 Detailed dry runs for every problem so you can visualize pointer movement
• ⚠️ High-ROI interview insights to avoid common Linked List bugs

✅ If you’re short on time, focus on the sections:
Must-Know Patterns, Templates, and Dry Runs
Interview Insights

Introduction

Linked Lists are where pointers shine. Unlike arrays, they don’t give you direct access by index — instead, you have to traverse and manipulate the structure node by node.

This pattern teaches you how to:

• Traverse, reverse, merge, and manipulate nodes
• Use fast/slow pointers for elegant solutions
• Spot cycles, detect intersections, and work with complex structures

---

📌 When to Use Linked List Patterns

Reach for these techniques when:

• You’re working with ListNode objects (custom linked lists)
• You're told O(1) insertion/deletion is required
• You need to reverse or reorder a structure
• You’re asked to detect cycles, intersection, or midpoints
• You see two-pointer behavior on nodes

---

🧠 Core Techniques

---

🧪 Problem Walkthroughs

These are the most commonly asked Linked List problems that map to core patterns:

---

Must-Know Patterns, Templates, and Dry Runs

🔹 Pattern: Reversal

Used in: Leetcode #206 – "Reverse a Linked List"

Goal: Reverse the direction of a singly linked list, in-place.

Input: 1 → 2 → 3 → 4 → null

Output: 4 → 3 → 2 → 1 → null

---

🔹 What we would do (High-Level)

• Use 3 pointers: prev, curr, and next.
• At each step:
  • Save curr.next in next
  • Point curr.next to prev
  • Move both prev and curr forward

---

🔹 Template

ListNode prev = null; 
ListNode curr = head; 

while (curr != null) { 
    ListNode next = curr.next; // Save next node 
    curr.next = prev;          // Reverse the link 
    prev = curr;               // Move prev ahead 
    curr = next;               // Move curr ahead 
} 
return prev; // New head of reversed list

---

🔹 Dry Run

Input: 1 → 2 → 3 → 4 → null

---

🔹 Pattern: Fast & Slow Pointers

Used in: Leetcode #141 – "Linked List Cycle"

Goal: Return true if a linked list contains a cycle (loop), false otherwise

Input: 3 → 2 → 0 → -4 → (points back to 2)

Output: true

---

🔹 What we would do (High-Level)

• Use two pointers: slow and fast
• Move slow by 1, fast by 2
• If they meet → cycle exists
• If fast hits null → no cycle

---

🔹 Template

ListNode slow = head, fast = head; 

while (fast != null && fast.next != null) { 
    slow = slow.next; 
    fast = fast.next.next; 

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

---

🔹 Dry Run

Input: 3 → 2 → 0 → -4 → (back to 2)

✅ Output: true

---

🔹 Pattern: Two Pointers (Offset Technique)

Used in: Leetcode #19 – "Remove N-th Node From End of List"

Goal: Delete the N-th node from the end of a singly linked list

Input: 1 → 2 → 3 → 4 → 5, n = 2

Output: 1 → 2 → 3 → 5

---

🔹 What we would do (High-Level)

• Use a dummy node pointing to head (handles edge case)
• Move fast pointer n steps ahead
• Then move both fast and slow until fast.next == null
• slow.next is the node to delete → skip it

---

🔹 Template

ListNode dummy = new ListNode(0); 
dummy.next = head; 

ListNode fast = dummy; 
ListNode slow = dummy; 

// Move fast ahead by n steps 
for (int i = 0; i < n; i++) { 
    fast = fast.next; 
} 

// Move both until fast.next == null 
while (fast.next != null) { 
    fast = fast.next; 
    slow = slow.next; 
} 

// Skip the node 
slow.next = slow.next.next; 

return dummy.next;

---

🔹 Dry Run

Input: 1 → 2 → 3 → 4 → 5, n = 2

Step 1: Move fast ahead 2 steps

• fast is at node 3

Step 2: Move both fast and slow

Now slow.next = 4 — we skip it → 3.next = 5

✅ Final Output: 1 → 2 → 3 → 5

🔹 Pattern: Merge + Dummy Node

Used in: Leetcode #21 – "Merge Two Sorted Lists" Goal: Merge two sorted linked lists into one sorted linked list Input: l1 = 1 → 3 → 4, l2 = 1 → 2 → 4 Output: 1 → 1 → 2 → 3 → 4 → 4

---

🔹 What we would do (High-Level)

• Use a dummy node to simplify edge cases
• Use a tail pointer to build the new list
• At each step, compare values of l1 and l2
• Attach the smaller node and move that list’s pointer forward

---

🔹 Template

ListNode dummy = new ListNode(0);
ListNode tail = dummy;

while (l1 != null && l2 != null) {
    if (l1.val < l2.val) {
        tail.next = l1;
        l1 = l1.next;
    } else {
        tail.next = l2;
        l2 = l2.next;
    }
    tail = tail.next;
}

tail.next = (l1 != null) ? l1 : l2;

return dummy.next;

---

🔹 Dry Run

Input: l1 = 1 → 3 → 4, l2 = 1 → 2 → 4

✅ Output: 1 → 1 → 2 → 3 → 4 → 4

---

🔹 Pattern: Cycle Start Logic

Used in: Leetcode #142 – "Linked List Cycle II" Goal: If a cycle exists, return the node where the cycle begins Input: 1 → 2 → 3 → 4 → 5 → 6 → (points back to 3) Output: Node with value 3

---

🔹 What we would do (High-Level)

• Use fast/slow pointers to detect if a cycle exists
• Once a meeting point is found, reset one pointer to head
• Move both pointers one step at a time
• The point where they meet again is the start of the cycle

---

🔹 Template

ListNode slow = head, fast = head;

// Step 1: Detect cycle
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) break;
}

// No cycle
if (fast == null || fast.next == null) return null;

// Step 2: Find cycle start
slow = head;
while (slow != fast) {
    slow = slow.next;
    fast = fast.next;
}

return slow;

---

🔹 Dry Run

Input: 1 → 2 → 3 → 4 → 5 → 6 → (points back to 3)

• slow and fast meet at node 5
• reset slow to head

✅ Output: node with value 3

---

🔹 Pattern: Midpoint + Reverse + Merge

Used in: Leetcode #143 – "Reorder List" Goal: Rearrange list to: first → last → second → second-last → ... Input: 1 → 2 → 3 → 4 → 5 Output: 1 → 5 → 2 → 4 → 3

---

🔹 What we would do (High-Level)

1. Use fast/slow to find middle
2. Reverse second half
3. Merge first and reversed second half

---

🔹 Template

// Step 1: Find middle
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

// Step 2: Reverse second half
ListNode second = reverse(slow.next);
slow.next = null;

// Step 3: Merge both halves
ListNode first = head;
while (second != null) {
    ListNode tmp1 = first.next;
    ListNode tmp2 = second.next;

    first.next = second;
    second.next = tmp1;

    first = tmp1;
    second = tmp2;
}

---

🔹 Dry Run

Input: 1 → 2 → 3 → 4 → 5

• Step 1: middle is 3
• Step 2: reverse 4 → 5 → becomes 5 → 4
• Step 3: merge

✅ Final: 1 → 5 → 2 → 4 → 3

---

🔹 Pattern: HashMap / Interleaving Clone

Used in: Leetcode #138 – "Copy List with Random Pointer" Goal: Create a deep copy of a list with .next and .random pointers Input: A → B → C with arbitrary .random links Output: A' → B' → C' (deep copy, same structure)

---

🔹 What we would do (High-Level)

1. Interleave original and copied nodes: A → A' → B → B'...
2. Assign random pointers to copied nodes
3. Separate the two lists into original and cloned

---

🔹 Template

// Step 1: Interleave clone nodes
Node curr = head;
while (curr != null) {
    Node copy = new Node(curr.val);
    copy.next = curr.next;
    curr.next = copy;
    curr = copy.next;
}

// Step 2: Assign random pointers
curr = head;
while (curr != null) {
    if (curr.random != null)
        curr.next.random = curr.random.next;
    curr = curr.next.next;
}

// Step 3: Separate cloned list
curr = head;
Node pseudoHead = new Node(0), copyCurr = pseudoHead;
while (curr != null) {
    copyCurr.next = curr.next;
    curr.next = curr.next.next;
    curr = curr.next;
    copyCurr = copyCurr.next;
}

return pseudoHead.next;

---

🔹 Dry Run

Input: A → B → C with A.random → C, B.random → A, C.random → B

• Step 1: Interleave → A → A' → B → B' → C → C'
• Step 2: Assign randoms using curr.random.next
• Step 3: Detach clone list

✅ Output: A' → B' → C' (deep copy with randoms)

---

Interview Insights

• ✅ Use a dummy node when deleting or inserting near the head — it prevents null pointer bugs and simplifies code.
• ✅ Always save next = curr.next before changing links — especially in reversal problems, to avoid losing the rest of the list.
• ✅ Watch for null checks before accessing node.next — edge cases like single-node or empty lists often break code.
• ✅ Set .next = null when splitting or reversing — failing to break the link can cause accidental cycles or infinite loops.
• ✅ Use .val, not node references, when comparing linked list values — useful in problems like Palindrome LL.

---

This should help cover most of what's important to know about Linked Lists from an interview perspective.