Hamropedia

DSA · Topic 6 of 18 · Core Structures

Linked List

Draw the boxes. Save next before you change a pointer, and add a dummy head to remove edge cases.

By Manoj Kumar Thapa

AI Software Engineer ·

11 problems · O(n) time, O(1) space

Step 1 Understand it

Remember it by

Draw the boxes. Save next before you change a pointer, and add a dummy head to remove edge cases.

Watch it happen

AnimationLinked lists: rewire the arrows, and keep a pointer to what you would lose
Read the animation as text
  1. Each node only knows the node after it. To reverse the list, walk it once and flip each arrow to point backwards. prev starts at None, curr at the head.
  2. Save nxt = curr.next (2) first — otherwise flipping the arrow would lose the rest of the list.
  3. curr.next = prev: 1 now points back to None. Then step forward: prev = 1, curr = 2.
  4. Save nxt = curr.next (3) first — otherwise flipping the arrow would lose the rest of the list.
  5. curr.next = prev: 2 now points back to 1. Then step forward: prev = 2, curr = 3.
  6. Save nxt = curr.next (4) first — otherwise flipping the arrow would lose the rest of the list.
  7. curr.next = prev: 3 now points back to 2. Then step forward: prev = 3, curr = 4.
  8. Save nxt = curr.next (None) first — otherwise flipping the arrow would lose the rest of the list.
  9. curr.next = prev: 4 now points back to 3. Then step forward: prev = 4, curr = None.
  10. curr is None: done. prev is the new head. Answer: [4, 3, 2, 1]. One pass, O(n) time, and only three extra pointers, O(1) space.

The idea

Each node points to the next one; there are no indexes. Most problems are pointer rewiring (reverse, merge, remove) or two pointers moving at different speeds or with a gap (find the middle, detect a cycle, the n-th from the end).

Picture it

flowchart LR
  subgraph Before
    A1["1"] --> A2["2"] --> A3["3"] --> N1["None"]
  end
  subgraph After
    B3["3"] --> B2["2"] --> B1["1"] --> N2["None"]
  end
Reversing doesn't move nodes; it turns every arrow around, one node at a time (prev, curr, next).

Analogy

A treasure hunt where each clue tells you where the next one is. To reverse the hunt, you rewrite each clue to point back — but read where it pointed before you overwrite it.

Where the analogy breaks

Treasure-hunt clues stay in place. In code, once you overwrite node.next without saving it, the rest of the list is lost for good.

More detail

What it is

Imagine you are following a treasure hunt where each clue tells you where to find the next one. Each clue card has two parts: the message on it (the data) and the directions to the next clue (the pointer). A linked list works in the same way: every node stores some data and a reference that leads you to the next node in the chain. If you want to reach the 5th clue, you cannot teleport to it; you must start at the first card and follow the trail one clue at a time. Linked lists behave like that too: to reach the 5th node, you begin at the head and move through each node in order, unlike an array where you can directly jump to any element using its index.

When to use it

  • When you need fast O(1) insertions or deletions at the ends.
  • When you do NOT need random access (like array[5]).
  • When building Stacks, Queues, or LRU Caches.

How it works

You always start by holding the head node. To traverse the list, you use a loop: while(curr != null) and simply jump to the next item via curr = curr.next;. When modifying the list (like insertions/deletions), you carefully rearrange the .next pointers before deleting anything so you don't lose the rest of the chain!

Example walkthrough

Input: head = [1,2,3], reverse it

  1. Node 1: Point next to null. Prev=1, Curr=2
  2. Node 2: Point next to 1. Prev=2, Curr=3
  3. Node 3: Point next to 2. Prev=3, Curr=null
  4. Curr is null, loop ends. New head is 3! Return [3,2,1]

Result: [3, 2, 1]

Related patterns

  • Fast & Slow Pointers: Using two pointers moving at different speeds (e.g. 1 step vs 2 steps) to find the middle or detect cycles.

Step 2 Recognise it

Words that signal it

  • The input is a linked list (ListNode)
  • 'Reverse', 'reorder', 'merge', 'remove the n-th node from the end'
  • 'Cycle', 'middle of the list'
  • 'O(1) extra space' with a list

Don't confuse it with

  • Arrays: No index access: you can't jump to the middle or the end, so you use fast/slow pointers instead.
  • Arrays & Hashing: A hash set finds a cycle with O(n) memory; fast and slow pointers find it with O(1).

Gut check

Linked list in the input? → think dummy node, prev/curr/next, or fast and slow.

How to recognise it in an interview

The input provides a ListNode or explicitly mentions 'Linked List'.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

python
def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next          # 1. save what comes next
        curr.next = prev         # 2. point backwards
        prev, curr = curr, nxt   # 3. step forward
    return prev                  # new head

def middle(head):
    slow = fast = head
    while fast and fast.next:    # fast moves 2, slow moves 1
        slow, fast = slow.next, fast.next.next
    return slow                  # slow is in the middle
The same template in Java
text
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next; // Save the rest of the list
            curr.next = prev;              // Reverse the pointer
            prev = curr;                   // Move prev forward
            curr = nextTemp;               // Move curr forward
        }
        return prev;
    }
}

Dummy node

python
def remove_value(head, target):
    dummy = ListNode(0, head)      # a fake node before the real head
    prev = dummy
    while prev.next:
        if prev.next.val == target:
            prev.next = prev.next.next   # removing the head is no longer a special case
        else:
            prev = prev.next
    return dummy.next
TimeO(n)
SpaceO(1)

Common mistakes

  • Losing the rest of the list by changing curr.next before saving it.
  • Special-casing the head instead of using a dummy node in front of it.
  • In fast/slow, checking fast.next without first checking fast.
  • Null Pointer Exceptions. You must constantly check if (curr != null && curr.next != null) before accessing properties.
  • Forgetting to handle edge cases like empty lists (head == null).

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

Easy example: Reverse Linked List

Input: 1 → 2 → 3 → 4

currreversed part (prev)still to do
11 → None2 → 3 → 4
22 → 1 → None3 → 4
33 → 2 → 1 → None4
44 → 3 → 2 → 1 → NoneNone

Result: [4, 3, 2, 1]

Notice: Three variables are all you need: where you came from (prev), where you are (curr), and where you go next (nxt).

python
def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    return prev

Medium example: Remove Nth Node From End of List

Input: 1 → 2 → 3 → 4 → 5, n = 2

stepslowfast
move fast n + 1 = 3 steps aheaddummy3
move both one step14
move both one step25
move both one step3None
fast is None → skip slow.next (4)3None

Result: [1, 2, 3, 5]

Notice: Keep a gap of n + 1 between the pointers. When fast falls off the end, slow is just before the node to remove — in one pass.

python
def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n + 1):        # open a gap of n + 1
        fast = fast.next
    while fast:
        slow, fast = slow.next, fast.next
    slow.next = slow.next.next    # skip the n-th from the end
    return dummy.next

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Easy

  1. Reverse Linked List Easy

    Reverse a singly linked list.

    Show answer

    Technique: Pointer reversal (prev, curr, next)

    The clue: 'Reverse' a linked list.

    The trick: Save next, point curr back to prev, step forward.

  2. Merge Two Sorted Lists Easy

    Merge two sorted linked lists into one sorted list.

    Show answer

    Technique: Dummy node + two pointers

    The clue: Two sorted lists → take the smaller head each time.

    The trick: Use a dummy node, attach the smaller node, advance that list, then attach whatever is left.

  3. Linked List Cycle Easy

    Decide whether a linked list has a cycle, using O(1) memory.

    Show answer

    Technique: Fast and slow pointers

    The clue: 'Cycle' in a linked list, constant memory.

    The trick: Fast moves two steps, slow one; if they ever meet, there's a cycle.

Medium

  1. Reorder List Medium

    Reorder L0 → L1 → … → Ln into L0 → Ln → L1 → Ln−1 → ….

    Show answer

    Technique: Find middle + reverse + merge

    The clue: Taking from the front and back alternately.

    The trick: Find the middle (fast/slow), reverse the second half, then weave the two halves together.

  2. Remove Nth Node From End of List Medium

    Remove the n-th node from the end of a linked list in one pass.

    Show answer

    Technique: Two pointers with a gap + dummy node

    The clue: 'n-th from the end' without knowing the length.

    The trick: Move fast n + 1 steps ahead of slow (from a dummy); when fast reaches the end, slow.next is the node to remove.

  3. Copy List With Random Pointer Medium

    Deep-copy a linked list whose nodes also have a random pointer.

    Show answer

    Technique: Hash map from old node to new node

    The clue: Copy with extra pointers that can point anywhere.

    The trick: First pass: create every copy in a map old → new. Second pass: set next and random through the map.

  4. Add Two Numbers Medium

    Add two numbers stored as reversed digit lists.

    Show answer

    Technique: Simultaneous traversal with a carry

    The clue: Digits in reverse order = column addition from the ones.

    The trick: Walk both lists together adding digits plus carry; keep going while either list or the carry remains.

  5. Find The Duplicate Number Medium

    Numbers 1 … n fill an array of n + 1; find the repeated one in O(1) extra space without changing the array.

    Show answer

    Technique: Floyd's cycle detection on indexes

    The clue: Values are valid indexes, so i → nums[i] forms a linked list with a cycle.

    The trick: Fast/slow to meet inside the cycle, then restart one pointer from 0; they meet at the duplicate.

  6. LRU Cache Medium

    Design a cache with get and put in O(1) that evicts the least recently used item.

    Show answer

    Technique: Hash map + doubly linked list

    The clue: O(1) lookups plus O(1) 'move to most recent' and 'evict oldest'.

    The trick: The map finds nodes; the doubly linked list keeps usage order. Move a node to the front when used; evict from the back.

Hard

  1. Merge K Sorted Lists Hard

    Merge k sorted linked lists into one sorted list.

    Show answer

    Technique: Min-heap (or divide and conquer)

    The clue: Repeatedly need the smallest head among k lists.

    The trick: Put each list's head in a min-heap; pop the smallest, attach it, push its next. O(N log k).

  2. Reverse Nodes In K Group Hard

    Reverse the nodes of a linked list k at a time.

    Show answer

    Technique: Group reversal with a dummy node

    The clue: Reverse in fixed-size chunks; leftovers stay as they are.

    The trick: For each group, check that k nodes exist, reverse them, and reconnect the previous group's tail to the new head.

What to say in the interview

'I'll use a dummy node at the beginning to gracefully handle edge cases where the head of the list might change or be deleted.'

Follow-up prep

How do you detect if a Linked List goes in a circle forever? (Hint: Fast & Slow pointers).