DevPath
Tracks

Linked Lists

Nodes joined by pointers: how singly and doubly linked lists work, plus the reverse, dummy-node and fast/slow pointer patterns.

beginner40 min#linked-list#pointers#two-pointers#cycle-detection

Prerequisites: Arrays and Dynamic Arrays, Memory, References, and Pointers

Why it matters

Linked lists are the simplest structure built from nodes and references, so they are the training ground for pointer thinking. The same skills carry over to trees, graphs, hash-table chains and LRU caches. They are also a favorite interview topic: reversing a list, finding a cycle, or merging two lists tests whether you can manipulate references without losing the rest of the structure.

Intuition

An array is a row of lockers; a linked list is a scavenger hunt. Each clue (a node) holds a value and a note saying where the next clue is. You only ever hold the first clue, called the head, and you must follow notes one at a time to reach anything else. In exchange, adding a clue in the middle is easy: write a new note and change one old note to point at it. Nothing has to slide over.

head
 |
 v
[1|*]--->[2|*]--->[3|*]--->[4|/]      "/" means next is null / None

Here is the same idea as a picture, first singly linked and then doubly linked.

1
head
2
3
4
null
A singly linked list. Each node holds a value and an arrow to the next node; the last arrow points to null. You hold only the head.
1
head
2
3
4
null
A doubly linked list has arrows both ways, so from any node you can step forward or backward.

A doubly linked list adds a second note, prev, pointing backwards. That lets you delete a node when you hold only that node (you can reach both neighbors) and walk in either direction, at the cost of one extra reference per node and more links to keep consistent.

How it works

  • Node: an object with a value and a next reference. The last node's next is null.
  • Access by position requires walking from the head, so get(i) is O(i).
  • Insert or delete after a known node rewires one or two references, so it is O(1) once you are standing there. Finding the spot is what costs O(n).
  • Tail pointer: keep a reference to the last node and appending becomes O(1) too.
  • Dummy (sentinel) node: put a fake node before the head. Then inserting or removing the first real node follows the same code as any other node, which removes a whole class of special cases.
  • Pointer to a node, not to a value: when you write cur.next = cur.next.next you are changing which node a reference points at. The skipped node is not modified; it simply becomes unreachable and the garbage collector reclaims it.

The three patterns worth memorizing:

  1. Reverse: walk once, and for each node save next, flip node.next to point at the previous node, then advance. Three moving references (prev, cur, next), O(n) time and O(1) space.
  2. Fast and slow pointers (Floyd): slow moves one step and fast moves two. If there is a cycle, fast eventually laps slow and they meet. If fast reaches the end, there is no cycle. The same trick finds the middle: when fast hits the end, slow is halfway.
  3. Dummy node plus a trailing pointer: used for deleting by value, merging sorted lists, and removing the n-th node from the end (advance one pointer n steps ahead first).

Reversing is easiest to see as arrows flipping one at a time. Step through reversing 1 -> 2 -> 3 -> 4; the green node is cur and the amber node is prev.

1234
Start: prev is null, cur is node 1. All arrows point right.
step 1 / 5

Reverse in place: each step flips one arrow, using only three references (prev, cur, next).

Fast and slow pointers can find the middle. Using the list 5 -> 4 -> 2 -> 1 from the code below, slow moves one node per step and fast moves two.

5
slow, fast
4
2
1
null
Both pointers start at the head.
step 1 / 3

When fast falls off the end, slow is at the middle. With 4 nodes it lands on the second middle node, the value 2.

Now the same pointers on a list that loops back. Node 1 points to node 4, so the tail never ends.

5421
slow and fast both start at node 5.
step 1 / 4

Inside a loop the fast pointer gains one node per step on the slow pointer, so it must eventually land on it.

OperationTimeNotes
Access i-th itemO(n)Must walk from the head
Insert / delete at headO(1)Rewire head
Insert / delete after a known nodeO(1)Singly: delete needs the previous node
Search by valueO(n)No random access, no binary search
AppendO(1) with tail pointerO(n) without it
Reverse / cycle check / find middleO(n) time, O(1) spaceOne pass with a few references

Code: reverse, delete, middle and cycle detection

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt
 
 
def from_list(xs):
    dummy = tail = Node(None)
    for x in xs:
        tail.next = Node(x)
        tail = tail.next
    return dummy.next
 
 
def to_str(head):
    parts = []
    while head:
        parts.append(str(head.val))
        head = head.next
    return " -> ".join(parts)
 
 
def reverse(head):
    prev = None
    while head:
        nxt = head.next      # remember the rest
        head.next = prev     # flip the arrow
        prev, head = head, nxt
    return prev
 
 
def remove_value(head, target):
    dummy = Node(None, head)  # dummy node: head needs no special case
    cur = dummy
    while cur.next:
        if cur.next.val == target:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return dummy.next
 
 
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
 
 
def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow.val
 
 
head = from_list([1, 2, 3, 4, 5])
print(to_str(head))
head = reverse(head)
print(to_str(head))
head = remove_value(head, 3)
print(to_str(head))
print(middle(head))
print(has_cycle(head))
tail = head
while tail.next:
    tail = tail.next
tail.next = head.next  # create a loop
print(has_cycle(head))

Both versions print:

1 -> 2 -> 3 -> 4 -> 5
5 -> 4 -> 3 -> 2 -> 1
5 -> 4 -> 2 -> 1
2
False
True

The list has 4 nodes after the delete, so middle returns the second of the two middle nodes (value 2). The last two lines show cycle detection before and after we link the tail back into the list.

Common pitfalls

  • Losing the rest of the list: overwriting node.next before saving it orphans every node after it.
  • Null dereference: fast.next.next crashes when fast.next is null. Always check fast and fast.next first.
  • Forgetting the head case: deleting or inserting at the head changes what the caller holds. Use a dummy node and return dummy.next.
  • Accidental cycles: after relinking nodes (for example while reversing part of a list), make sure the new tail's next is null.
  • Believing linked lists are faster than arrays for inserts: you still pay O(n) to find the position, and nodes scattered in memory hurt CPU cache behavior. In practice arrays and dynamic arrays win on most workloads.
  • Comparing nodes by value: cycle detection compares node identity (is in Python, === in JavaScript), not stored values, since duplicates are normal.

Practice

Find the middle node easy

Hint

Move one pointer twice as fast as another. Where is the slow one when the fast one finishes?

Show solution

Start slow and fast at the head. While fast and fast.next exist, advance slow by one and fast by two. When the loop ends, slow is at the middle (the second middle for even lengths). One pass, O(n) time, O(1) space, and no need to know the length.

Merge two sorted lists medium

Hint

Use a dummy node and a tail pointer, and always attach the smaller head.

Show solution

Create dummy and tail = dummy. While both lists are non-empty, attach whichever head value is smaller to tail.next and advance both that list and tail. When one list runs out, attach the remainder of the other in a single assignment. Return dummy.next. O(n + m) time, O(1) extra space, and it reuses the existing nodes.

Remove the n-th node from the end medium

Hint

You can only walk forward. Create a gap of n nodes between two pointers.

Show solution

Use a dummy node. Advance lead n steps from the dummy, then move lead and trail together until lead.next is null. Now trail.next is the node to remove, so set trail.next = trail.next.next. One pass, O(1) space. The dummy handles the case where the head itself is removed.

Find where a cycle begins hard

Hint

After the pointers meet, restart one from the head. What does moving both one step at a time reveal?

Show solution

Run Floyd's algorithm until slow and fast meet inside the cycle. Reset one pointer to the head and advance both one step at a time; they meet exactly at the cycle's entry node. Reason: if the head is a steps from the entry and the meeting point is b steps into the cycle of length c, then a is congruent to c - b modulo c, so walking a more steps from the meeting point lands on the entry. O(n) time, O(1) space.

Interview questions

  1. Array vs linked list? Arrays give O(1) indexing and great cache locality; linked lists give O(1) splicing when you already hold the node and never need a big contiguous block. Most real code prefers arrays.
  2. How do you detect a cycle without extra memory? Floyd's fast and slow pointers. A hash set of visited nodes also works but uses O(n) space.
  3. Why use a doubly linked list in an LRU cache? With a hash map from key to node, you can unlink any node and move it to the front in O(1), which needs the prev pointer.
  4. How would you reverse a list recursively? Reverse the rest, then make the next node point back at the current one and set the current next to null. It uses O(n) stack space, so the iterative version is safer for long lists.

Interviewers look for: using a dummy node, checking null cases (empty list, one node), saying out loud which pointers you save before rewiring, and stating O(1) space for the pointer tricks.

Quick check

In a singly linked list you hold a reference to a node X (not the head). What can you delete in O(1)?

Finished this lesson?

Further resources

Related lessons