# Linked List Interview Patterns

Source: https://www.techinterview.org/post/3233466900/linked-list-patterns/
Updated: 2026-04-17 · techinterview.org

Linked list problems trip up candidates because pointer manipulation is easy to mess up under pressure. These patterns cover every common linked list interview question.

## ListNode Definition and Basic Operations


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

# Build a list from array (useful for testing)
def build_list(arr):
    dummy = ListNode(0)
    curr = dummy
    for val in arr:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next

# Convert list back to array
def to_array(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result
```


## Fast-Slow Pointer

Two pointers moving at different speeds. Fast moves 2 steps per iteration, slow moves 1. When fast reaches the end, slow is at the middle.


```
# Detect cycle (Floyd's algorithm)
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Find cycle start
def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Move one pointer to head, advance both at speed 1
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

# Find middle of list
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # For even-length lists, returns second middle node

# Find kth node from end (k=1 means last node)
def kth_from_end(head, k):
    fast = slow = head
    for _ in range(k):
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    return slow
```


## Reverse a Linked List

LC 206. The iterative approach with three pointers is the most reliable in an interview.


```
# Iterative - O(n) time O(1) space
def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next   # save before breaking link
        curr.next = prev        # reverse the link
        prev = curr             # advance prev
        curr = next_node        # advance curr
    return prev

# Recursive
def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

# Reverse a sublist from position left to right (LC 92)
def reverse_between(head, left, right):
    dummy = ListNode(0, head)
    prev = dummy
    for _ in range(left - 1):
        prev = prev.next
    curr = prev.next
    for _ in range(right - left):
        next_node = curr.next
        curr.next = next_node.next
        next_node.next = prev.next
        prev.next = next_node
    return dummy.next
```


## Merge Two Sorted Lists

LC 21. The dummy head trick eliminates the special case of an empty result list.


```
def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2  # attach remaining
    return dummy.next
```


Always use a dummy head when building a new list or when the head node might change. Return dummy.next as the result.

## Merge K Sorted Lists

LC 23. Two approaches: min-heap (simpler to implement) or divide-and-conquer.


```
import heapq

# Min-heap approach - O(N log k) where N = total nodes, k = number of lists
def merge_k_lists(lists):
    dummy = ListNode(0)
    curr = dummy
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

# Divide and conquer - repeatedly merge pairs of lists
def merge_k_lists_dc(lists):
    if not lists:
        return None
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(merge_two_lists(l1, l2))
        lists = merged
    return lists[0]
```


The heap approach needs a tiebreaker (the index i) because Python compares tuple elements in order and ListNode doesn't support comparison.

## Reorder List

LC 143: reorder L0 -> Ln -> L1 -> Ln-1 -> L2 -> ... Three steps: find middle, reverse second half, merge two halves.


```
def reorder_list(head):
    if not head or not head.next:
        return

    # Step 1: find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: reverse second half
    second = slow.next
    slow.next = None  # cut the list
    prev = None
    while second:
        tmp = second.next
        second.next = prev
        prev = second
        second = tmp
    second = prev

    # Step 3: merge first and reversed second halves
    first = head
    while second:
        tmp1 = first.next
        tmp2 = second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2
```


## Deep Copy with Random Pointers

LC 138: copy a linked list where each node has a next and a random pointer.


```
class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

# Two-pass with hash map - O(n) time O(n) space
def copy_random_list(head):
    if not head:
        return None
    old_to_new = {}
    curr = head
    # First pass: create all new nodes
    while curr:
        old_to_new[curr] = Node(curr.val)
        curr = curr.next
    # Second pass: wire up next and random pointers
    curr = head
    while curr:
        if curr.next:
            old_to_new[curr].next = old_to_new[curr.next]
        if curr.random:
            old_to_new[curr].random = old_to_new[curr.random]
        curr = curr.next
    return old_to_new[head]

# O(1) space weave approach: interleave copied nodes with originals
def copy_random_list_o1(head):
    if not head:
        return None
    # Step 1: insert copy after each original node
    curr = head
    while curr:
        copy = Node(curr.val)
        copy.next = curr.next
        curr.next = copy
        curr = copy.next
    # Step 2: set random pointers on copies
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next
    # Step 3: separate the two lists
    dummy = Node(0)
    copy_curr = dummy
    curr = head
    while curr:
        copy_curr.next = curr.next
        curr.next = curr.next.next
        copy_curr = copy_curr.next
        curr = curr.next
    return dummy.next
```


## LRU Cache with Doubly Linked List

O(1) get and put using a hash map plus doubly linked list. The list maintains access order; hash map gives O(1) node lookup.


```
class DLinkedNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        # Dummy head and tail avoid edge cases
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)
        return node.val

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = DLinkedNode(key, value)
        self.cache[key] = node
        self._add_to_front(node)
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]
```


## Common Pitfalls

- **Null check before .next:** Always verify a node is not None before accessing .next. Pattern: `while curr and curr.next`

- **Losing track of nodes when relinking:** Save next_node = curr.next before changing curr.next. Draw the state before writing code.

- **Off-by-one in position problems:** Decide if positions are 0-indexed or 1-indexed upfront. LC problems usually use 1-indexed.

- **Forgetting to terminate the list:** After splitting or reversing, set the tail's .next to None to avoid cycles in the result.

- **Modifying head node:** Use a dummy head when the result list might start at a different node than the input.

## Pattern: Dummy Head Node

The dummy head node is the single most useful linked list trick. It eliminates all special cases for operations at the head of the list.


```
# Remove all nodes with value val (LC 203)
def remove_elements(head, val):
    dummy = ListNode(0, head)
    curr = dummy
    while curr.next:
        if curr.next.val == val:
            curr.next = curr.next.next  # skip the node
        else:
            curr = curr.next
    return dummy.next  # never need to check if head changed
```


Use a dummy head whenever: you might delete the head node, you are building a new list from scratch, or the head of the result depends on the algorithm's logic.

Meta coding interviews frequently test linked list manipulation. See common patterns for [Meta interview: linked list problems](https://www.techinterview.org/post/3233460272/meta-interview-guide-2026-facebook-instagram-whatsapp-engineering/).

Uber coding rounds include linked list and pointer manipulation. See patterns for [Uber interview: linked list and pointer problems](https://www.techinterview.org/post/3233460273/uber-interview-guide-2026-dispatch-systems-geospatial-algorithms-and-marketplace-engineering/).

Atlassian coding rounds include linked list problems. See patterns for [Atlassian interview: linked list and data structure problems](https://www.techinterview.org/post/3233459919/atlassian-interview/).