Linked List Pattern Explained

What is a Linked List?

A linked list is a linear data structure where elements (nodes) are connected through pointers rather than stored in contiguous memory. Each node contains data and a reference to the next node. Unlike arrays, linked lists excel at insertions and deletions but sacrifice random access.

Singly vs Doubly Linked Lists

Singly Linked List: Each node has a next pointer only. You can only traverse forward. Most interview problems use singly linked lists.

// Singly Linked List Node
class ListNode {
  val: number
  next: ListNode | null

  constructor(val: number = 0, next: ListNode | null = null) {
    this.val = val
    this.next = next
  }
}

// Example: 1 -> 2 -> 3 -> null
const head = new ListNode(1, new ListNode(2, new ListNode(3)))

Doubly Linked List: Each node has both next and prev pointers. You can traverse in both directions, which simplifies certain operations like deletion.

// Doubly Linked List Node
class DoublyListNode {
  val: number
  next: DoublyListNode | null
  prev: DoublyListNode | null

  constructor(val: number = 0) {
    this.val = val
    this.next = null
    this.prev = null
  }
}

// Used in: LRU Cache, browser history, text editors

When to Use Linked List Techniques

Consider linked list patterns when:

• In-place reversal needed - Reverse a portion or the entire list without extra space
• Cycle detection - Determine if a list has a loop using fast/slow pointers
• Merging lists - Combine sorted lists efficiently
• Finding middle element - Use fast/slow pointers to find the midpoint in one pass
• Removing nth element from end - Use two pointers with fixed distance
• Reordering nodes - Interleave, partition, or rearrange without creating new nodes

Pattern Variations

1. Two Pointers: Fast and Slow

The fast/slow pointer technique (also called Floyd's algorithm or tortoise and hare) uses two pointers moving at different speeds. The slow pointer moves one step at a time, while the fast pointer moves two steps. This pattern is essential for:

• Finding the middle of a linked list
• Detecting cycles
• Finding the start of a cycle

function findMiddle(head: ListNode | null): ListNode | null {
  if (!head) return null

  let slow: ListNode | null = head
  let fast: ListNode | null = head

  // Fast moves 2x speed, so when fast reaches end,
  // slow is at the middle
  while (fast !== null && fast.next !== null) {
    slow = slow!.next
    fast = fast.next.next
  }

  return slow
}

// Example: 1 -> 2 -> 3 -> 4 -> 5
// When fast reaches 5, slow is at 3 (middle)
// For even length: 1 -> 2 -> 3 -> 4
// Returns second middle (3)

2. Dummy Head Technique

Using a dummy node (sentinel) before the actual head simplifies edge cases. When the head might change (deletions, insertions at front), the dummy node eliminates special-case handling.

function removeElements(head: ListNode | null, val: number): ListNode | null {
  // Dummy node handles edge case where head needs removal
  const dummy = new ListNode(0, head)
  let current = dummy

  while (current.next !== null) {
    if (current.next.val === val) {
      // Skip the node with matching value
      current.next = current.next.next
    } else {
      current = current.next
    }
  }

  // Return actual head (skip dummy)
  return dummy.next
}

// Without dummy: Would need special logic for removing head
// With dummy: Same logic handles all positions

3. In-Place Reversal

Reversing a linked list (or a portion of it) is a fundamental technique. The key insight is tracking three pointers: previous, current, and next.

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null
  let current = head

  while (current !== null) {
    // Save next before we overwrite current.next
    const next = current.next

    // Reverse the link
    current.next = prev

    // Move prev and current one step forward
    prev = current
    current = next
  }

  // prev is now the new head
  return prev
}

// Visual: 1 -> 2 -> 3 -> null
// Step 1: null <- 1    2 -> 3 -> null
// Step 2: null <- 1 <- 2    3 -> null
// Step 3: null <- 1 <- 2 <- 3
// Result: 3 -> 2 -> 1 -> null

Common Problems & Solutions

Problem 1: Detect Cycle in Linked List

Question: Given the head of a linked list, determine if it has a cycle. A cycle exists if a node can be reached again by following the next pointers.

function hasCycle(head: ListNode | null): boolean {
  if (!head || !head.next) return false

  let slow: ListNode | null = head
  let fast: ListNode | null = head

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

    // If they meet, there's a cycle
    if (slow === fast) {
      return true
    }
  }

  // Fast reached the end - no cycle
  return false
}

// Why it works:
// If there's a cycle, fast will eventually "lap" slow
// They'll meet inside the cycle
// If no cycle, fast reaches null

Follow-up: Find where the cycle begins.

function detectCycle(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return null

  let slow: ListNode | null = head
  let fast: ListNode | null = head

  // Phase 1: Detect if cycle exists
  while (fast !== null && fast.next !== null) {
    slow = slow!.next
    fast = fast.next.next

    if (slow === fast) {
      // Phase 2: Find cycle start
      // Reset slow to head, keep fast at meeting point
      slow = head

      while (slow !== fast) {
        slow = slow!.next
        fast = fast!.next
      }

      return slow // Cycle start
    }
  }

  return null // No cycle
}

// Math insight: Distance from head to cycle start equals
// distance from meeting point to cycle start (going around)

Problem 2: Merge Two Sorted Lists

Question: Merge two sorted linked lists into one sorted list.

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  // Dummy head simplifies building the result
  const dummy = new ListNode(0)
  let tail = dummy

  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      tail.next = list1
      list1 = list1.next
    } else {
      tail.next = list2
      list2 = list2.next
    }
    tail = tail.next
  }

  // Attach remaining nodes (one list may be longer)
  tail.next = list1 !== null ? list1 : list2

  return dummy.next
}

// Example:
// list1: 1 -> 3 -> 5
// list2: 2 -> 4 -> 6
// Result: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Problem 3: Remove Nth Node From End

Question: Given a linked list, remove the nth node from the end and return the head. Do it in one pass.

function removeNthFromEnd(
  head: ListNode | null,
  n: number
): ListNode | null {
  const dummy = new ListNode(0, head)
  let first: ListNode | null = dummy
  let second: ListNode | null = dummy

  // Move first pointer n+1 steps ahead
  // This creates a gap of n nodes between first and second
  for (let i = 0; i <= n; i++) {
    first = first!.next
  }

  // Move both pointers until first reaches end
  while (first !== null) {
    first = first.next
    second = second!.next
  }

  // second.next is the node to remove
  second!.next = second!.next!.next

  return dummy.next
}

// Example: 1 -> 2 -> 3 -> 4 -> 5, n = 2
// Gap of 2: when first is at end, second is at 3
// Remove 4 (2nd from end): 1 -> 2 -> 3 -> 5

Problem 4: Reverse Linked List II (Partial Reversal)

Question: Reverse the nodes between positions left and right (1-indexed).

function reverseBetween(
  head: ListNode | null,
  left: number,
  right: number
): ListNode | null {
  if (!head || left === right) return head

  const dummy = new ListNode(0, head)
  let prev = dummy

  // Move prev to node before 'left' position
  for (let i = 1; i < left; i++) {
    prev = prev.next!
  }

  // Start reversing from the 'left' node
  let current = prev.next

  // Reverse nodes between left and right
  for (let i = 0; i < right - left; i++) {
    // Take the next node and move it to just after prev
    const nextNode = current!.next
    current!.next = nextNode!.next
    nextNode!.next = prev.next
    prev.next = nextNode
  }

  return dummy.next
}

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

Time & Space Complexity

Pro Tips

• Always use dummy head: When the head might change, a dummy node eliminates edge cases. Return dummy.next at the end.
• Draw the pointers: Linked list manipulation is visual. Sketch the before/after state of each pointer change.
• Save next before modifying: When reversing or reordering, always save current.next before you overwrite it.
• Check null early: Handle !head and !head.nextat the start to avoid null pointer errors.
• Fast/slow is O(1) space: Prefer it over using a Set for cycle detection when asked for constant space.
• Recursion works but costs space: Recursive solutions use O(n) stack space, while iterative solutions use O(1).

Practice Problems

Ready to test your understanding? Try these LeetCode problems:

• Easy: Reverse Linked List, Merge Two Sorted Lists, Linked List Cycle, Remove Linked List Elements
• Medium: Remove Nth Node From End, Add Two Numbers, Reorder List, Sort List, Copy List with Random Pointer
• Hard: Merge k Sorted Lists, Reverse Nodes in k-Group

Continue Learning

• Two Pointers Pattern - The fast/slow technique used extensively in linked lists
• Binary Search Guide - Arrays vs linked lists: when to use each
• Dynamic Programming Guide - Optimize recursive linked list solutions with memoization
• Start Practicing - Apply linked list patterns to real interview problems