Overview

A linked list stores each element in its own node with a pointer to the next node. There is no index arithmetic, so reaching the k-th element takes O(k) steps — but inserting or removing a node you already hold is O(1), because only a couple of pointers change. Doubly linked lists add a pointer back to the previous node, which is what makes structures like an LRU cache possible.

Interviewers like linked lists because they reveal how carefully you handle state. Almost every problem reduces to three moves: use a dummy node so the head is not a special case, save next before you overwrite it, and use two pointers moving at different speeds to find middles and cycles.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Access k-th elementO(k)
Insert / delete at a known nodeO(1)
Search by valueO(n)
ReverseO(n) time, O(1) space

Patterns to recognise

Dummy head + tail

Use it for: Building a new list: merge, partition, remove elements.

tail.next = node; tail = node; return dummy.next.

Reverse in place

Use it for: Reverse a list or part of it, palindrome check, reorder list.

Keep prev/curr/next; reverse a sublist by reconnecting its ends afterwards.

Fast & slow / gap pointers

Use it for: Middle node, cycle detection, n-th node from end.

Different speeds find middles and cycles; a fixed gap of n finds the n-th from the end.

Code template

Reverse a list and detect a cycle
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse(head):
    prev = None
    while head:
        nxt = head.next          # save before rewiring
        head.next = prev
        prev, head = head, nxt
    return prev


def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

Common mistakes

  • Overwriting node.next before saving it loses the rest of the list.
  • Dereferencing null: always check fast and fast.next before stepping twice.
  • Test empty lists, single nodes and two nodes — most bugs live there.
  • Draw the pointers on paper before coding a rewiring step.

Quick check

Three questions on Linked Lists. Get all three right to earn +15 XP.

  1. Given a pointer to the head, inserting a new node at the front of a singly linked list costs:

  2. Reaching the k-th node of a linked list costs:

  3. What does a dummy (sentinel) head node simplify?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Linked Lists?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor