Linked Lists

A Python listlist is a contiguous array under the hood — fast random access, slow insertion in the middle. A linked list flips that trade-off: no random access, but $O(1)$ insertion or deletion once you’re holding the right node. Interviewers love linked lists because they test whether you can manipulate raw pointers correctly, not just call a library function.

What you’ll learn

Singly vs doubly linked lists, and the NodeNode class that builds both.
Why arrays win on cache locality but linked lists win on $O(1)$ splice.
Iterative traversal, and the classic iterative reversal pointer dance.
Floyd’s Tortoise and Hare cycle detection, in $O(n)$ time and $O(1)$ space.
Merging two sorted linked lists — the building block behind merge sort.

Why a linked list at all

A Python listlist (really a dynamic array) gives you $O(1)$ index access but $O(n)$ insertion/deletion anywhere except the end, because every element after the insertion point has to shift. A linked list stores each value in its own node, plus a pointer to the next node. Nothing shifts — you just rewire a couple of pointers.

diagram Singly linked list: nodes and next pointers mermaid

  graph LR
    H["head"] --> N1["10"]
    N1 --> N2["20"]
    N2 --> N3["30"]
    N3 --> N4["40"]
    N4 --> NUL["None"]

The cost: to reach the 4th node you must walk through the first three — there is no list[3]list[3]-style jump. Traversal is always $O(n)$ .

The `NodeNode` class and a singly linked list

singly_linked_list.py

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
 
class SinglyLinkedList:
    def __init__(self):
        self.head = None
 
    def append(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
            return
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = node
 
    def to_list(self):
        out = []
        cur = self.head
        while cur is not None:
            out.append(cur.value)
            cur = cur.next
        return out
 
 
ll = SinglyLinkedList()
for v in [10, 20, 30, 40]:
    ll.append(v)
 
print("traversal:", ll.to_list())

singly_linked_list.py

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
 
class SinglyLinkedList:
    def __init__(self):
        self.head = None
 
    def append(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
            return
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = node
 
    def to_list(self):
        out = []
        cur = self.head
        while cur is not None:
            out.append(cur.value)
            cur = cur.next
        return out
 
 
ll = SinglyLinkedList()
for v in [10, 20, 30, 40]:
    ll.append(v)
 
print("traversal:", ll.to_list())

Doubly linked lists: pointers both ways

A doubly linked list adds a prevprev pointer, so you can walk backward and delete a node in $O(1)$ given a reference to it (no need to find its predecessor first).

doubly_linked_list.py

class DNode:
    def __init__(self, value, prev=None, next=None):
        self.value = value
        self.prev = prev
        self.next = next
 
 
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
 
    def append(self, value):
        node = DNode(value)
        if self.head is None:
            self.head = self.tail = node
            return
        node.prev = self.tail
        self.tail.next = node
        self.tail = node
 
    def forward(self):
        out, cur = [], self.head
        while cur is not None:
            out.append(cur.value)
            cur = cur.next
        return out
 
    def backward(self):
        out, cur = [], self.tail
        while cur is not None:
            out.append(cur.value)
            cur = cur.prev
        return out
 
 
dll = DoublyLinkedList()
for v in [1, 2, 3]:
    dll.append(v)
 
print("forward: ", dll.forward())
print("backward:", dll.backward())

doubly_linked_list.py

class DNode:
    def __init__(self, value, prev=None, next=None):
        self.value = value
        self.prev = prev
        self.next = next
 
 
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
 
    def append(self, value):
        node = DNode(value)
        if self.head is None:
            self.head = self.tail = node
            return
        node.prev = self.tail
        self.tail.next = node
        self.tail = node
 
    def forward(self):
        out, cur = [], self.head
        while cur is not None:
            out.append(cur.value)
            cur = cur.next
        return out
 
    def backward(self):
        out, cur = [], self.tail
        while cur is not None:
            out.append(cur.value)
            cur = cur.prev
        return out
 
 
dll = DoublyLinkedList()
for v in [1, 2, 3]:
    dll.append(v)
 
print("forward: ", dll.forward())
print("backward:", dll.backward())

Reversing a list: the pointer dance

Reversal is the single most common linked-list interview question. No new nodes are allocated — you just walk the list once, flipping each nextnext pointer to point backward.

sketch Pointer surgery: reversing a linked list p5.js

Each step flips one next pointer to point backward instead of forward — no node ever moves, only the arrows change direction.

reverse_linked_list.py

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
 
def build(values):
    head = tail = None
    for v in values:
        node = Node(v)
        if head is None:
            head = tail = node
        else:
            tail.next = node
            tail = node
    return head
 
 
def to_list(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out
 
 
def reverse_iterative(head):
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next     # save the rest of the list before we overwrite it
        curr.next = prev    # flip this node's pointer backward
        prev = curr         # prev advances to curr
        curr = nxt          # curr advances to the node we saved
    return prev              # prev ends up as the new head
 
 
head = build([1, 2, 3, 4, 5])
print("before:", to_list(head))
new_head = reverse_iterative(head)
print("after: ", to_list(new_head))

reverse_linked_list.py

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
 
def build(values):
    head = tail = None
    for v in values:
        node = Node(v)
        if head is None:
            head = tail = node
        else:
            tail.next = node
            tail = node
    return head
 
 
def to_list(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out
 
 
def reverse_iterative(head):
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next     # save the rest of the list before we overwrite it
        curr.next = prev    # flip this node's pointer backward
        prev = curr         # prev advances to curr
        curr = nxt          # curr advances to the node we saved
    return prev              # prev ends up as the new head
 
 
head = build([1, 2, 3, 4, 5])
print("before:", to_list(head))
new_head = reverse_iterative(head)
print("after: ", to_list(new_head))

Three variables (prevprev, currcurr, nxtnxt), one pass, zero extra allocation: $O(n)$ time, $O(1)$ space.

Detecting a cycle: Floyd’s Tortoise and Hare

If a buggy nextnext pointer (or an intentional circular structure) loops back on itself, naive traversal never terminates. Two pointers moving at different speeds solve it without any extra memory: if there’s a cycle, the fast pointer eventually laps the slow one.

cycle_detection.py

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
 
def build_with_cycle(values, cycle_at=None):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if cycle_at is not None:
        nodes[-1].next = nodes[cycle_at]   # last node points back into the list
    return nodes[0]
 
 
def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next          # moves 1 step
        fast = fast.next.next     # moves 2 steps
        if slow is fast:           # they met -- must be a cycle
            return True
    return False
 
 
clean = build_with_cycle([1, 2, 3, 4])
looped = build_with_cycle([1, 2, 3, 4], cycle_at=1)   # 4 -> back to node at index 1
 
print("clean list has cycle: ", has_cycle(clean))
print("looped list has cycle:", has_cycle(looped))

cycle_detection.py

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
 
def build_with_cycle(values, cycle_at=None):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if cycle_at is not None:
        nodes[-1].next = nodes[cycle_at]   # last node points back into the list
    return nodes[0]
 
 
def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next          # moves 1 step
        fast = fast.next.next     # moves 2 steps
        if slow is fast:           # they met -- must be a cycle
            return True
    return False
 
 
clean = build_with_cycle([1, 2, 3, 4])
looped = build_with_cycle([1, 2, 3, 4], cycle_at=1)   # 4 -> back to node at index 1
 
print("clean list has cycle: ", has_cycle(clean))
print("looped list has cycle:", has_cycle(looped))

Merging two sorted linked lists

The core routine behind linked-list merge sort: walk both lists once, always taking the smaller head, and re-link nodes — no new nodes are ever created.

merge_two_sorted_lists.py

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
 
def build(values):
    head = tail = None
    for v in values:
        node = Node(v)
        if head is None:
            head = tail = node
        else:
            tail.next = node
            tail = node
    return head
 
 
def to_list(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out
 
 
def merge_sorted(a, b):
    dummy = Node(0)   # placeholder so we never special-case an empty result
    tail = dummy
    while a is not None and b is not None:
        if a.value <= b.value:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a if a is not None else b   # attach whatever's left
    return dummy.next
 
 
a = build([1, 3, 5])
b = build([2, 4, 6, 8])
print("merged:", to_list(merge_sorted(a, b)))

merge_two_sorted_lists.py

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
 
def build(values):
    head = tail = None
    for v in values:
        node = Node(v)
        if head is None:
            head = tail = node
        else:
            tail.next = node
            tail = node
    return head
 
 
def to_list(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out
 
 
def merge_sorted(a, b):
    dummy = Node(0)   # placeholder so we never special-case an empty result
    tail = dummy
    while a is not None and b is not None:
        if a.value <= b.value:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a if a is not None else b   # attach whatever's left
    return dummy.next
 
 
a = build([1, 3, 5])
b = build([2, 4, 6, 8])
print("merged:", to_list(merge_sorted(a, b)))

Time and space complexity

Operation	Linked list	Python `listlist` (array)
Access by index	$O(n)$	$O(1)$
Search by value	$O(n)$	$O(n)$
Insert/delete at head	$O(1)$	$O(n)$
Insert/delete at tail (tracked)	$O(1)$	$O(1)$ amortized
Insert/delete given a node reference	$O(1)$	$O(n)$
Auxiliary space per element	extra pointer(s)	none

LeetCode problem set

#	Problem	Difficulty	The twist
206	Reverse Linked List	Easy	The iterative pointer dance above, from scratch
141	Linked List Cycle	Easy	Floyd’s Tortoise and Hare, exactly as shown
21	Merge Two Sorted Lists	Easy	The dummy-head merge routine above

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 206 — Reverse Linked List · Easy

Problem. Reverse a singly linked list and return the new head.

Constraints. 0 <= number of nodes <= 50000 <= number of nodes <= 5000, -5000 <= Node.val <= 5000-5000 <= Node.val <= 5000.

Examples. [1,2,3,4,5][1,2,3,4,5] gives [5,4,3,2,1][5,4,3,2,1] · [1,2][1,2] gives [2,1][2,1] · [][] gives [][]

Editorial

Three references and a fixed order of operations. prevprev trails behind, headhead walks forward, and nxtnxt preserves the link you are about to destroy.

Time $O(n)$ . Space $O(1)$ .

The empty-list case works with no guard: the loop never runs and prevprev is already NoneNone, which is the correct answer. That is a small sign the design is right.

The recursive version is elegant but $O(n)$ stack: reverse the tail, then attach headhead to its end. At 5000 nodes that is within Python’s default limit, but only just — worth mentioning.

This is the core operation behind In-place Linked List Reversal, where the same four lines reverse a segment rather than the whole list.

Follow-ups: “Reverse only positions m..nm..n (LC 92)?” — the same loop, anchored by a dummy head. “Reverse in groups of kk (LC 25)?” — count kk ahead, reverse, relink, repeat. “Recursively?” — have it ready, and mention the stack cost.

LC 203 — Remove Linked List Elements · Easy

Problem. Remove every node whose value equals valval, and return the new head.

Constraints. 0 <= number of nodes <= 10^40 <= number of nodes <= 10^4, 1 <= Node.val <= 501 <= Node.val <= 50, 0 <= val <= 500 <= val <= 50.

Examples. [1,2,6,3,4,5,6], val = 6[1,2,6,3,4,5,6], val = 6 gives [1,2,3,4,5][1,2,3,4,5] · [7,7,7,7], val = 7[7,7,7,7], val = 7 gives [][]

Editorial

The dummy head gives the real head a predecessor, so deleting it is no different from deleting any other node — no if node is headif node is head branch anywhere.

Time $O(n)$ . Space $O(1)$ .

The rule that matters: prevprev advances only in the elseelse branch. After unlinking, prevprev is the predecessor of the next node, which may also need removing. Advancing unconditionally means [7,7,7,7][7,7,7,7] leaves stray sevens behind — that case must return [][].

Follow-ups: “Remove the nnth node from the end (LC 19)?” — two pointers with a fixed gap, both starting at the dummy. “Remove duplicates from a sorted list (LC 83 / LC 82)?” — 83 keeps one of each; 82 removes every duplicated value, which makes the dummy essential. “Recursively?” — head.next = removeElements(head.next, val)head.next = removeElements(head.next, val), returning head.nexthead.next when it matches.

LC 876 — Middle of the Linked List · Easy

Problem. Return the middle node. If there are two middle nodes, return the second one.

Constraints. 1 <= number of nodes <= 1001 <= number of nodes <= 100.

Examples. [1,2,3,4,5][1,2,3,4,5] gives the node 33 · [1,2,3,4,5,6][1,2,3,4,5,6] gives the node 44

Editorial

If fastfast moves twice as fast as slowslow, then when fastfast reaches the end slowslow has covered half the distance.

Time $O(n)$ , one pass. Space $O(1)$ .

The loop condition is the whole subtlety, and it is worth memorising both forms:

while fast and fast.nextwhile fast and fast.next — slowslow lands on the second middle of an even list. [1,2][1,2] returns node 22. This is what LC 876 wants.
while fast.next and fast.next.nextwhile fast.next and fast.next.next — slowslow lands on the first middle, i.e. the end of the first half. That is what you want when splitting a list, as in Reorder List and merge sort.

Choosing the wrong one is a common source of off-by-one bugs in list problems, and the two-element case is the fastest way to tell them apart.

Follow-ups: “Return the first middle instead?” — switch conditions. “Detect a cycle (LC 141)?” — same pointers; they meet if a cycle exists. “Find the cycle’s start (LC 142)?” — after they meet, reset one to the head and step both by one.

Recap

Nodes + pointers trade array cache-locality for $O(1)$ splice given a node reference — traversal is always $O(n)$ , there’s no random access.
Reversal is pure pointer rewiring: prevprev, currcurr, nxtnxt, one pass, $O(1)$ space.
Floyd’s Tortoise and Hare detects a cycle in $O(n)$ time and $O(1)$ space — no visited-set required.
Merging two sorted lists is $O(n + m)$ and re-links existing nodes instead of allocating new ones.

Next: Hash Tables — trading the linked list’s sequential walk for average- $O(1)$ lookup by key.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Linked Lists

What you’ll learn

Why a linked list at all

The NodeNode class and a singly linked list

Doubly linked lists: pointers both ways

Reversing a list: the pointer dance

Detecting a cycle: Floyd’s Tortoise and Hare

Merging two sorted linked lists

Time and space complexity

LeetCode problem set

Practice — real LeetCode problems

LC 206 — Reverse Linked List · Easy

LC 203 — Remove Linked List Elements · Easy

LC 876 — Middle of the Linked List · Easy

Recap

Was this page helpful?

The `NodeNode` class and a singly linked list