T TestsWorld
← All topic guides

Linked lists: formulas, shortcuts & solved examples

What it is

A linked list is a chain of nodes where each node holds a value and a pointer to the next node. Unlike arrays, nodes are not contiguous, so inserting or deleting at a known position is cheap, but reaching the k-th element requires walking from the head. Interviewers like linked lists because pointer manipulation exposes careless thinking quickly.

Key rules

Types

  • Singly linked: each node points to the next; the last points to NULL.
  • Doubly linked: each node also points to the previous node, allowing O(1) deletion when you hold the node.
  • Circular: the last node points back to the head.

Operation costs (singly linked, n nodes)

Operation Cost
Insert at head O(1)
Insert at tail O(n), or O(1) with a tail pointer
Access k-th node O(k)
Search O(n)
Delete after a known node O(1)
Delete a given value O(n)

Node in Python

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

Standard techniques

  • Dummy (sentinel) head: simplifies edge cases when the real head may change.
  • Slow and fast pointers: slow moves one step, fast moves two. Used for the middle node and cycle detection (Floyd's algorithm).
  • Gap of k: move one pointer k steps ahead, then move both together; when the leader hits the end, the follower is k from the end.
  • Three-pointer reversal: prev, curr, next.

Shortcuts

  1. Middle node. When fast reaches the end, slow is at the middle. For an even count this standard loop lands on the second of the two middle nodes.
  2. Cycle check. If slow and fast ever meet, there is a cycle; if fast hits NULL, there is none. O(n) time, O(1) space.
  3. Draw three boxes. Before coding any pointer change, sketch three nodes and redraw arrows step by step. Most bugs come from overwriting next before saving it.

Solved examples

Example 1: Reverse a list

prev, curr = None, head      # head: 10 -> 20 -> 30 -> 40 -> 50
while curr:
    nxt = curr.next
    curr.next = prev
    prev = curr
    curr = nxt
head = prev

Solution. Each iteration flips one arrow. After five iterations, prev points to 50 and the list reads 50 -> 40 -> 30 -> 20 -> 10. Time O(n), space O(1).

Example 2: Find the middle

List: 1 -> 2 -> 3 -> 4 -> 5 -> 6.

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
print(slow.val)

Solution. Positions (slow, fast): start (1, 1), then (2, 3), (3, 5), (4, NULL past 6). The loop stops since fast is NULL. Output 4, the second middle of an even-length list. For 1 to 5 it would print 3.

Example 3: Remove the 2nd node from the end

List: 7 -> 14 -> 21 -> 28 -> 35, remove the 2nd from the end (28).

dummy = Node(0, head)
lead = lag = dummy
for _ in range(2 + 1):
    lead = lead.next
while lead:
    lead = lead.next
    lag = lag.next
lag.next = lag.next.next
head = dummy.next

Solution. Lead starts 3 steps ahead (at 21). Both move until lead passes 35; lag is then at 21, just before 28. Skipping it gives 7 -> 14 -> 21 -> 35. The dummy node means removing the head itself (k = 5) needs no special case.

Example 4: Merge two sorted lists

Lists: 1 -> 4 -> 9 and 2 -> 3 -> 10 -> 12.

def merge(a, b):
    dummy = tail = Node(0)
    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

Solution. Compare heads repeatedly: 1, 2, 3, 4, 9, then list a is empty, so the remainder 10 -> 12 is attached directly. Result 1 -> 2 -> 3 -> 4 -> 9 -> 10 -> 12, in O(m + n) time and O(1) extra space. This is the merge step of merge sort on linked lists.

Common mistakes

  1. Losing the rest of the list. Changing curr.next before saving it in a temporary variable disconnects everything after curr.
  2. Not handling an empty list or a single node. Always test head = None and a one-node list.
  3. Dereferencing NULL in the fast pointer loop. The condition must check both fast and fast.next.
  4. Forgetting to update the head. After reversal or deleting the first node, return the new head; the old variable still points to the old first node.
  5. Assuming linked lists beat arrays for everything. They have poor cache locality and O(n) indexing; arrays usually win unless you insert and delete in the middle often.

Practice now: https://www.testsworld.com/mocks

Ready to practise Linked lists?
Take a free mock test

Related guides