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
| Operation | Cost |
|---|---|
| Access k-th element | O(k) |
| Insert / delete at a known node | O(1) |
| Search by value | O(n) |
| Reverse | O(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
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
struct ListNode {
int val;
ListNode* next;
ListNode(int v = 0, ListNode* n = nullptr) : val(v), next(n) {}
};
ListNode* reverse(ListNode* head) {
ListNode* prev = nullptr;
while (head) {
ListNode* nxt = head->next; // save before rewiring
head->next = prev;
prev = head;
head = nxt;
}
return prev;
}
bool hasCycle(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == 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.
-
Given a pointer to the head, inserting a new node at the front of a singly linked list costs:
Point the new node at the old head and update the head. Nothing shifts.
-
Reaching the k-th node of a linked list costs:
There is no index arithmetic: you must follow k next pointers.
-
What does a dummy (sentinel) head node simplify?
Every real node then has a predecessor, so the head needs no special handling.
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.
- Reverse Linked ListLeetCode Easy +20
- Merge Two Sorted ListsLeetCode Easy +20
- Linked List CycleLeetCode Easy +20
- Middle of the Linked ListLeetCode Easy +20
- Remove Nth Node From End of ListLeetCode Medium +40
- Reorder ListLeetCode Medium +40
- Add Two NumbersLeetCode Medium +40
- Copy List with Random PointerLeetCode Medium +40
- Reverse Nodes in k-GroupLeetCode Hard +70
Stuck on Linked Lists?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor