Linked Lists: Pointers and Two-Pointer Tricks | Algorithms Tutorial

This chapter covers singly and doubly linked lists, cycle detection, and the two-pointer technique that shows up everywhere.

Why Linked Lists Exist

A linked list is a sequence of nodes, each holding a value and a pointer to the next node. Compared to a dynamic array:

Insert at the front: O(1) for linked list, O(n) for array.
Insert at a known node: O(1) for linked list, O(n) for array.
Random index access: O(n) for linked list, O(1) for array.
Cache locality: terrible for linked list (nodes scattered in memory), great for array.

In Python, linked lists are rarely the right answer. deque gives you O(1) at both ends without the overhead of separate node objects. Use linked lists when:

An interview asks for one.
You're implementing something else (LRU cache, graph adjacency, LFU).
You're working in C or C++ where cache costs differ from Python.

That said, linked lists are interview favorites, and the two-pointer tricks transfer to arrays and strings.

A Minimal Node

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

Build a list manually:

head = Node(1, Node(2, Node(3)))

head → 1 → 2 → 3 → None.

Walking:

def walk(head):
    node = head
    while node:
        print(node.val)
        node = node.next

walk(head)
# 1
# 2
# 3

Common Operations

Prepend (Insert at Head)

def prepend(head, val):
    return Node(val, head)

head = prepend(head, 0)
# 0 → 1 → 2 → 3

O(1). Old head becomes the new head's next.

Append (Insert at Tail)

def append(head, val):
    if head is None:
        return Node(val)
    node = head
    while node.next:
        node = node.next
    node.next = Node(val)
    return head

O(n). We walk to the tail. To make it O(1), keep a tail pointer alongside head.

Delete by Value

def delete(head, val):
    if head is None:
        return None
    if head.val == val:
        return head.next
    node = head
    while node.next and node.next.val != val:
        node = node.next
    if node.next:
        node.next = node.next.next
    return head

O(n). Find the node whose next holds the target; skip over it.

Reverse

def reverse(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    return prev

O(n), O(1) space. Classic three-pointer dance. Commit it to memory; it comes up constantly.

Doubly Linked Lists

Each node has next and prev.

class DNode:
    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

Benefits:

Delete a known node in O(1): node.prev.next = node.next and vice versa.
Walk backwards.
LRU caches need this.

Costs:

Every node has an extra pointer (more memory).
Every insert/delete updates two pointers.

For scratch work, stick with singly linked lists. Reach for doubly linked when you need delete-by-node.

Two Pointers: Slow and Fast

The canonical linked-list trick: two pointers moving at different speeds.

Find the Middle Node

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

fast moves twice per step. When fast reaches the end, slow is at the middle. One pass, O(n) time, O(1) space.

Detect a 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 is fast:
            return True
    return False

If there's a cycle, the fast pointer eventually laps the slow one. If there isn't, the fast pointer reaches None. No extra memory.

Without two pointers, the straightforward "detect a cycle" uses a set of visited nodes (O(n) space). Two pointers bring it down to O(1).

Find the Start of the Cycle

After detecting the cycle, reset one pointer to head and walk both at the same speed; they meet at the cycle's start.

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

The math works out; trust it and memorize the shape.

Merging Two Sorted Lists

def merge(a, b):
    dummy = Node(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

The dummy node trick simplifies the head-of-list bookkeeping. You build the result with tail.next = ...; the dummy's next is the real head when you're done.

O(n + m) time, O(1) extra space.

Using Dummy Nodes

A dummy (sentinel) node removes the special case of "inserting at the head". You always have a previous node to work with.

def delete(head, val):
    dummy = Node(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == val:
            prev.next = prev.next.next
        else:
            prev = prev.next
    return dummy.next

Cleaner than the version without the dummy. Worth the allocation.

A Useful Linked-List Problem

Reorder List: Given L0 → L1 → L2 → L3 → ... → Ln-1 → Ln, produce L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ....

Three steps, each linked-list-classic:

Find the middle (slow/fast).
Reverse the second half.
Merge alternately.

def reorder(head):
    if not head or not head.next:
        return
    # 1. Find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # 2. Reverse second half
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    # 3. Merge alternately
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

Messy if you've never seen it. Clean once you recognize the three building blocks.

Complexity Quick Reference

Operation                  Singly LL    Doubly LL    Python list    deque
Access by index            O(n)         O(n)         O(1)           O(n)
Insert at head             O(1)         O(1)         O(n)           O(1)
Insert at tail (no tail)   O(n)         O(n)         O(1)*          O(1)
Insert at tail (w/ tail)   O(1)         O(1)         -              -
Delete a known node        O(n)**       O(1)         O(n)           O(n)
Search by value            O(n)         O(n)         O(n)           O(n)

* amortized. ** O(n) because you need the previous node to unlink.

When Not to Use Linked Lists

Often. In Python, the cache-friendly array beats the linked list at almost everything. Linked lists shine when:

You're implementing something specific (LRU cache, adjacency lists, bucket chains in a hash table).
You need true O(1) insert/delete at an already-known position.
You're in a language where cache behavior hurts less (C/C++ with manual memory layouts can be different).

The value of this chapter is less "always use linked lists" and more "understand two-pointer patterns that apply everywhere".

Common Pitfalls

Losing the head. Once you walk forward, you can't walk back. Save the head before iterating.

Off-by-one in slow/fast. while fast and fast.next is the canonical guard. Forget it and you crash on the last node.

Modifying while iterating. A delete changes next. Use a sentinel and iterate by prev.next.

Forgetting to set node.next = None at the end. Particularly when reversing or building. Leaves a cycle.

Reimplementing Python's deque. For real O(1) at both ends, use collections.deque. The linked-list exercise is pedagogical; the production code is deque.

Next Steps

Continue to 05-searching.md to find things fast.