Linked Lists: 8 Practice Problems with Solutions

The eight problems below are the linked-list questions that show up most often in technical interviews. Each one builds on the operations from the previous post — traversal, dummy heads, two pointers, and careful pointer reassignment. Work through each problem before you read the solution; just reading them is half the value.

The Node class we’ll use throughout:

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

And a helper for building lists from Python lists:

def from_list(values):
    dummy = Node(0)
    current = dummy
    for v in values:
        current.next = Node(v)
        current = current.next
    return dummy.next

def to_list(head):
    result = []
    while head is not None:
        result.append(head.value)
        head = head.next
    return result

1. Reverse Linked List

Problem. Given the head of a singly linked list, reverse the list and return the new head.

Example. 1 -> 2 -> 3 -> 4 -> 5 becomes 5 -> 4 -> 3 -> 2 -> 1.

Approach. Walk forward with prev, current, and a cached nxt. Flip each next pointer as you go.

def reverse_list(head):
    prev = None
    current = head
    while current is not None:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev

print(to_list(reverse_list(from_list([1, 2, 3, 4, 5]))))    # [5, 4, 3, 2, 1]

O(n) time, O(1) space. The recursive version is in the operations post.

2. Detect Cycle (Linked List Cycle I)

Problem. Given a linked list, return True if it contains a cycle, else False.

Approach. Slow pointer moves one step, fast pointer moves two. If there is a cycle they must meet. If not, fast falls off the end.

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

O(n) time, O(1) space.

3. Merge Two Sorted Lists

Problem. Merge two sorted singly linked lists into a single sorted list. Return its head.

Example. 1 -> 3 -> 5 and 2 -> 4 -> 6 → 1 -> 2 -> 3 -> 4 -> 5 -> 6.

Approach. Walk both lists with two pointers; at each step append the smaller value to the merged list. A dummy head keeps the “what about the first node?” case from appearing.

def merge_sorted(a, b):
    dummy = Node(0)
    tail = dummy
    while a is not None and b is not None:
        if a.value <= b.value:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a if a is not None else b
    return dummy.next

a = from_list([1, 3, 5])
b = from_list([2, 4, 6])
print(to_list(merge_sorted(a, b)))    # [1, 2, 3, 4, 5, 6]

O(n + m) time, O(1) extra space — we re-use the existing nodes.

4. Remove Nth Node From End of List

Problem. Remove the nth node from the end of the list and return the new head.

Example. Remove 2nd from end of 1 -> 2 -> 3 -> 4 -> 5 → 1 -> 2 -> 3 -> 5.

Approach. Two pointers, n steps apart. When the leading pointer hits the end, the trailing pointer is sitting on the predecessor of the doomed node.

Remove 2nd from end of 1 -> 2 -> 3 -> 4 -> 5:
Step 0 — advance fast by n+1 = 3 steps from dummy:
dummy ─► 1 ─► 2 ─► 3 ─► 4 ─► 5 ─► None
▲                 ▲
slow              fast
Step 1 — walk both until fast is None:
dummy ─► 1 ─► 2 ─► 3 ─► 4 ─► 5 ─► None
▲                       ▲
slow                    fast
slow.next (= 4) is the node to remove. Set slow.next = slow.next.next.

def remove_nth_from_end(head, n):
    dummy = Node(0, next=head)
    slow = fast = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast is not None:
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next
    return dummy.next

print(to_list(remove_nth_from_end(from_list([1, 2, 3, 4, 5]), 2)))    # [1, 2, 3, 5]

O(n) time, O(1) space, single pass.

5. Linked List Cycle II — Find the Start of the Cycle

Problem. Given a list that may contain a cycle, return the node where the cycle begins, or None if there is no cycle.

Approach. Two-phase Floyd. Phase one: detect the cycle as before. Phase two: reset one pointer to the head and walk both one step at a time. They meet at the start of the cycle.

The math: if L is the distance from head to cycle start, and C is the cycle length, the pointers meet at distance L mod C inside the cycle. Starting one pointer from the head and stepping both by one means they collide exactly at the cycle entrance.

head                cycle starts here
│                          │
▼                          ▼
┌───┐    ┌───┐    ┌───┐    ┌───┐    ┌───┐
│ 1 │───►│ 2 │───►│ 3 │───►│ 4 │───►│ 5 │
└───┘    └───┘    └───┘    └───┘    └───┘
▲              │
│              │
└──────────────┘
Phase 1: slow and fast meet somewhere in the cycle.
Phase 2: reset one pointer to head. Move both one step.
They meet at node 4 — the cycle start.

def cycle_start(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None
    if fast is None or fast.next is None:
        return None
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow

O(n) time, O(1) space. The Python while/else runs the else if the loop exited normally — a clean way to handle “no cycle found”.

6. Palindrome Linked List

Problem. Return True if the list reads the same forwards and backwards.

Example. 1 -> 2 -> 2 -> 1 → True. 1 -> 2 -> 3 → False.

Approach. Find the middle with slow/fast, reverse the second half, then compare both halves node by node. O(1) extra space.

def is_palindrome(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    # reverse second half starting at slow
    prev = None
    current = slow
    while current is not None:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt

    # compare
    left, right = head, prev
    while right is not None:
        if left.value != right.value:
            return False
        left = left.next
        right = right.next
    return True

print(is_palindrome(from_list([1, 2, 2, 1])))    # True
print(is_palindrome(from_list([1, 2, 3])))       # False

O(n) time, O(1) space. If you don’t mind O(n) extra space, the easier solution is to copy values into a Python list and compare with values == values[::-1].

7. Add Two Numbers

Problem. Two non-empty linked lists represent two non-negative integers. Each node holds a single digit. The digits are stored in reverse order (the 1s place is at the head). Return the sum as a linked list in the same format.

Example. 342 + 465 = 807, given as 2 -> 4 -> 3 and 5 -> 6 -> 4, returns 7 -> 0 -> 8.

Approach. Walk both lists together, adding digits and tracking a carry. A dummy head keeps the first-node case trivial.

def add_two_numbers(a, b):
    dummy = Node(0)
    tail = dummy
    carry = 0
    while a is not None or b is not None or carry:
        s = carry
        if a is not None:
            s += a.value
            a = a.next
        if b is not None:
            s += b.value
            b = b.next
        carry, digit = divmod(s, 10)
        tail.next = Node(digit)
        tail = tail.next
    return dummy.next

a = from_list([2, 4, 3])   # 342
b = from_list([5, 6, 4])   # 465
print(to_list(add_two_numbers(a, b)))    # [7, 0, 8] → 807

O(max(n, m)) time, O(max(n, m)) space for the output list.

8. Intersection of Two Linked Lists

Problem. Given two singly linked lists that may merge into a single list at some node, return that intersection node. If they don’t intersect, return None.

Example. Two lists that share their last three nodes — return the first shared node.

Approach. Two pointers. When one reaches the end, switch it to the other list’s head. They walk equal total distance — the length of A plus the length of B — and will meet at the intersection, or both arrive at None simultaneously.

List A:  a1 ─► a2 ─► c1 ─► c2 ─► c3 ─► None
▲
│
List B:        b1 ─► b2 ┘
Pointer P starts on A, then on B.
Pointer Q starts on B, then on A.
Both walk len(A) + len(B) nodes total → they sync at c1, the intersection.

def intersection(headA, headB):
    if headA is None or headB is None:
        return None
    p, q = headA, headB
    while p is not q:
        p = p.next if p is not None else headB
        q = q.next if q is not None else headA
    return p

O(n + m) time, O(1) space. The clever bit: if there is no intersection, both pointers eventually become None at the same time, so p is q is true and we return None.

A note on testing linked-list code

Linked-list bugs are easy to spot when you print the list at every step. Add a small helper and sprinkle it through your code while you debug:

def show(head):
    parts = []
    seen = set()
    while head is not None and id(head) not in seen:
        seen.add(id(head))
        parts.append(str(head.value))
        head = head.next
    if head is not None:
        parts.append("(cycle!)")
    print(" -> ".join(parts) + " -> None")

The seen set means you won’t loop forever if your list accidentally has a cycle — a saver during reversal debugging.

More practice

Try these without solutions:

1. Odd/Even Linked List — rearrange so odd-positioned nodes come before even-positioned ones, preserving relative order.
2. Swap Nodes in Pairs — given 1 -> 2 -> 3 -> 4, return 2 -> 1 -> 4 -> 3.
3. Reverse Nodes in k-Group — reverse every k consecutive nodes; if fewer than k remain, leave them as-is.
4. Copy List with Random Pointer — deep-copy a list where each node also has a random pointer to any other node.
5. Sort List — sort a linked list in O(n log n) using merge sort (use the middle-finding trick to split).
6. LRU Cache — implement an LRU cache backed by a doubly linked list and a hashmap.

If you can do these confidently, you have linked lists well in hand.

Recap

You now know:

• Reverse is the foundational three-pointer dance — cache next, flip, advance
• Floyd’s slow/fast finds cycles, middles, and cycle starts
• A dummy head removes the “what about the first node?” special case
• Two pointers n apart find the nth-from-end in one pass
• The intersection trick relies on two pointers walking equal total distance
• Add-two-numbers is a carry walk — the same shape as elementary-school addition

Next steps

Linked lists are the simplest pointer-based structure. The next post moves up one level: stacks and queues, which are usually built on top of linked lists or arrays and power everything from undo systems to BFS traversal.

→ Next: Stacks and Queues in DSA

Questions or feedback? Email codeloomdevv@gmail.com.