Skip to main content
Linked List Pattern

​
What is Linked List?

Linked List is a linear data structure where elements are connected via pointers. Unlike arrays, it allows O(1) insertions/deletions but O(n) access.
Quick Recognition: Problems involving pointer manipulation, in-place modifications, or two-pointer techniques on sequences. Keywords: “reverse”, “cycle”, “merge lists”, “middle node”.

​
Pattern Recognition Checklist

Use Linked List Patterns When

  • Detecting cycles (Floyd’s algorithm)
  • Finding middle element
  • Reversing all or part of list
  • Merging sorted lists
  • Checking palindrome structure
  • Removing duplicates

Common Techniques

  • Dummy head for edge cases
  • Fast/slow pointers for cycle/middle
  • Prev/curr/next for reversal
  • Two-pointer for nth from end
  • In-place to save space

​
When to Use

Fast and Slow Pointers

Cycle detection, finding middle

Reversal

Reverse entire list or portions

Merging

Merge sorted lists, intersection

Dummy Node

Simplify edge case handling

​
Pattern Variations

​
1. Fast and Slow Pointers (Floyd’s)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head):
    """Detect cycle in linked list"""
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    
    return False

def find_middle(head):
    """Find middle node (second middle if even length)"""
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow

​
2. Reverse Linked List

def reverse_list(head):
    """Reverse entire linked list"""
    prev = None
    current = head
    
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    
    return prev

def reverse_between(head, left, right):
    """Reverse nodes from position left to right"""
    dummy = ListNode(0, head)
    prev = dummy
    
    # Move to node before left
    for _ in range(left - 1):
        prev = prev.next
    
    # Reverse from left to right
    current = prev.next
    for _ in range(right - left):
        next_node = current.next
        current.next = next_node.next
        next_node.next = prev.next
        prev.next = next_node
    
    return dummy.next

​
3. Merge Two Sorted Lists

def merge_two_lists(l1, l2):
    """Merge two sorted linked lists"""
    dummy = ListNode(0)
    current = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    current.next = l1 or l2
    return dummy.next

​
4. Remove Nth Node From End

def remove_nth_from_end(head, n):
    """Remove nth node from end using two pointers"""
    dummy = ListNode(0, head)
    slow = fast = dummy
    
    # Move fast n+1 steps ahead
    for _ in range(n + 1):
        fast = fast.next
    
    # Move both until fast reaches end
    while fast:
        slow = slow.next
        fast = fast.next
    
    # Remove nth node
    slow.next = slow.next.next
    return dummy.next

​
Classic Problems

ProblemPatternKey Insight
Cycle DetectionFast/SlowFloyd’s algorithm
Middle of ListFast/SlowFast moves 2x speed
Reverse ListIterativeTrack prev, curr, next
Merge K ListsDivide/HeapMerge pairs or use min-heap
IntersectionLength DiffAlign starts then traverse
PalindromeReverse HalfReverse second half and compare

​
Interview Problems by Company

ProblemCompanyKey Concept
Reverse ListAll FAANGBasic reversal
Merge Two ListsAll FAANGTwo pointers
Delete NodeApple, AmazonNo prev access trick
Middle of ListAmazonFast/slow

​
Interview Tips

A dummy node simplifies edge cases when the head might change:
def solve(head):
    dummy = ListNode(0)
    dummy.next = head
    # ... operations ...
    return dummy.next  # New head

def reverse(head):
    prev, curr = None, head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev  # New head
  1. Detect cycle: Fast catches slow = cycle exists
  2. Find start: Reset one to head, move both at same speed
def find_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:  # Cycle found
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow  # Cycle start
    return None

​
Practice Problems

Reverse Linked List

Basic reversal technique

Linked List Cycle II

Find cycle start point

Merge K Sorted Lists

Divide and conquer or heap

LRU Cache

Doubly linked list + HashMap

​
Practice Roadmap

1

Day 1: Basic Operations

  • Solve: Reverse List, Merge Two Lists
  • Focus: Pointer manipulation
2

Day 2: Fast/Slow Pointers

  • Solve: Middle of List, Cycle Detection, Cycle II
  • Focus: Floyd’s algorithm
3

Day 3: In-Place Modifications

  • Solve: Reorder List, Palindrome Linked List
  • Focus: Combining techniques
4

Day 4: Advanced

  • Solve: LRU Cache, Merge K Lists, Reverse K Group
  • Focus: Design + complex operations
Interview Tip: Draw the linked list! Visualizing pointer changes helps avoid bugs. Always consider: What if head is null? What if only one node?