Autocoder

Linked list interview questions with worked solutions

Last updated 2026-11-19

A linked list has no random access, so every problem forces you to think in terms of pointers: who points to whom after each step, and what do you lose if you overwrite a pointer too early. Interviewers like these questions because small pointer mistakes show up immediately as lost nodes, cycles or null pointer errors.

The ten problems below build on three tools: a dummy head node to remove special cases, a reverse routine you can write without thinking, and a gap between two pointers. For cycle detection, middle-finding and palindromes, see fast and slow pointers questions. General practice advice is in the DSA coding round guide.

Problems10, easy to hard
LanguagesPython and Java
ToolsDummy head, reversal, gap pointers, heap

Node class used below

Every solution assumes a singly linked node with a value and a next pointer. Define it once and reuse it. Examples show lists such as 1 -> 2 -> 3 -> null.

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Habits that prevent pointer bugs

Use a dummy node before the head whenever the head itself might change, such as when deleting the first node or merging two lists. Save the next pointer before you overwrite it. Draw three nodes and trace the loop by hand before you submit.

Linked list interview questions with worked solutions: questions with worked answers

  1. 1

    Reverse a singly linked list.

    easy

    Walk the list with three references: prev (starts null), cur and a saved next. For each node, save cur.next, point cur.next at prev, then advance both prev and cur. When cur is null, prev is the new head. For 1 -> 2 -> 3 the result is 3 -> 2 -> 1. Time O(n), space O(1).. Edge cases: empty list, single node, two nodes.

    python
    def reverse_list(head):
        prev, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev, cur = cur, nxt
        return prev
    java
    import java.util.*;
    
    class Solution {
        static ListNode reverseList(ListNode head) {
            ListNode prev = null, cur = head;
            while (cur != null) {
                ListNode nxt = cur.next;
                cur.next = prev;
                prev = cur;
                cur = nxt;
            }
            return prev;
        }
    }
  2. 2

    Merge two sorted linked lists into one sorted list.

    easy

    Create a dummy node and a tail pointer. Repeatedly attach the smaller head of the two lists to the tail and advance that list. When one list ends, attach the rest of the other. The dummy node means you never special-case the first node. Taking the left list on ties keeps the merge stable. Time O(n + m), space O(1) because nodes are relinked.. Edge cases: one or both lists empty, equal values, lists of very different lengths.

    python
    def merge_two_lists(a, b):
        dummy = tail = ListNode()
        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
    java
    import java.util.*;
    
    class Solution {
        static ListNode mergeTwoLists(ListNode a, ListNode b) {
            ListNode dummy = new ListNode(0), tail = dummy;
            while (a != null && b != null) {
                if (a.val <= b.val) { tail.next = a; a = a.next; }
                else { tail.next = b; b = b.next; }
                tail = tail.next;
            }
            tail.next = a != null ? a : b;
            return dummy.next;
        }
    }
  3. 3

    Remove duplicates from a sorted linked list so each value appears once.

    easy

    Because equal values are adjacent, compare each node with its next. If they match, skip the next node by pointing cur.next at cur.next.next, and do not advance. Otherwise move on. Only advancing when no deletion happened handles runs of three or more. Time O(n), space O(1).. Edge cases: empty list, all values equal, no duplicates.

    python
    def delete_duplicates(head):
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head
    java
    import java.util.*;
    
    class Solution {
        static ListNode deleteDuplicates(ListNode head) {
            ListNode cur = head;
            while (cur != null && cur.next != null) {
                if (cur.val == cur.next.val) cur.next = cur.next.next;
                else cur = cur.next;
            }
            return head;
        }
    }
  4. 4

    Remove the nth node from the end in one pass.

    medium

    Start a dummy node before the head. Move a fast pointer n steps ahead, then move fast and slow together until fast.next is null. Now slow sits just before the node to delete, so set slow.next = slow.next.next. The dummy node handles removing the head itself. Time O(n), space O(1).. Edge cases: removing the head (n equals the length), a one-node list, n = 1 (the tail).

    python
    def remove_nth_from_end(head, n):
        dummy = ListNode(0, head)
        fast = slow = dummy
        for _ in range(n):
            fast = fast.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next
    java
    import java.util.*;
    
    class Solution {
        static ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(0, head), fast = dummy, slow = dummy;
            for (int i = 0; i < n; i++) fast = fast.next;
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return dummy.next;
        }
    }
  5. 5

    Add two numbers stored as linked lists of digits in reverse order.

    medium

    The lists start at the least significant digit, so add as you walk, like school arithmetic. Keep a carry; at each step sum the two digits (treat a missing node as 0) plus carry, store sum % 10 and carry sum / 10. Continue while either list or the carry remains, so a final carry becomes an extra node. Time O(max(n, m)), space O(max(n, m)) for the result.. Edge cases: different lengths, a final carry (99 + 1), both lists a single zero.

    python
    def add_two_numbers(a, b):
        dummy = tail = ListNode()
        carry = 0
        while a or b or carry:
            s = carry + (a.val if a else 0) + (b.val if b else 0)
            carry, digit = divmod(s, 10)
            tail.next = ListNode(digit)
            tail = tail.next
            a = a.next if a else None
            b = b.next if b else None
        return dummy.next
    java
    import java.util.*;
    
    class Solution {
        static ListNode addTwoNumbers(ListNode a, ListNode b) {
            ListNode dummy = new ListNode(0), tail = dummy;
            int carry = 0;
            while (a != null || b != null || carry != 0) {
                int s = carry + (a != null ? a.val : 0) + (b != null ? b.val : 0);
                carry = s / 10;
                tail.next = new ListNode(s % 10);
                tail = tail.next;
                if (a != null) a = a.next;
                if (b != null) b = b.next;
            }
            return dummy.next;
        }
    }
  6. 6

    Copy a linked list where each node also has a random pointer to any node or null.

    medium

    Make a first pass that creates a copy of every node and stores old to new in a hash map. A second pass wires next and random on each copy using the map; a missing key (null) gives null. The follow-up is the O(1) space version that interleaves copies between originals. Time O(n), space O(n).. Edge cases: empty list, random pointing to itself, random null on every node.

    python
    class Node:
        def __init__(self, val, next=None, random=None):
            self.val, self.next, self.random = val, next, random
    
    def copy_random_list(head):
        m = {}
        cur = head
        while cur:
            m[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:
            m[cur].next = m.get(cur.next)
            m[cur].random = m.get(cur.random)
            cur = cur.next
        return m.get(head)
    java
    import java.util.*;
    
    class Node {
        int val;
        Node next, random;
        Node(int val) { this.val = val; }
    }
    
    class Solution {
        static Node copyRandomList(Node head) {
            Map<Node, Node> m = new HashMap<>();
            for (Node cur = head; cur != null; cur = cur.next) m.put(cur, new Node(cur.val));
            for (Node cur = head; cur != null; cur = cur.next) {
                m.get(cur).next = m.get(cur.next);
                m.get(cur).random = m.get(cur.random);
            }
            return m.get(head);
        }
    }
  7. 7

    Reorder list: turn L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> ...

    medium

    Find the middle with slow and fast pointers, cut the list there, reverse the second half, then interleave the two halves node by node. Each step is simple; the care is in saving next pointers before relinking and in setting the first half tail to null. Time O(n), space O(1).. Edge cases: zero, one or two nodes (nothing to do), odd versus even length.

    python
    def reorder_list(head):
        if not head or not head.next:
            return
        slow = fast = head
        while fast.next and fast.next.next:
            slow, fast = slow.next, fast.next.next
        prev, cur = None, slow.next
        slow.next = None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        first, second = head, prev
        while second:
            n1, n2 = first.next, second.next
            first.next = second
            second.next = n1
            first, second = n1, n2
    java
    import java.util.*;
    
    class Solution {
        static void reorderList(ListNode head) {
            if (head == null || head.next == null) return;
            ListNode slow = head, fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode prev = null, cur = slow.next;
            slow.next = null;
            while (cur != null) {
                ListNode nxt = cur.next;
                cur.next = prev;
                prev = cur;
                cur = nxt;
            }
            ListNode first = head, second = prev;
            while (second != null) {
                ListNode n1 = first.next, n2 = second.next;
                first.next = second;
                second.next = n1;
                first = n1;
                second = n2;
            }
        }
    }
  8. 8

    Sort a linked list in O(n log n) time.

    medium

    Merge sort suits linked lists because splitting needs no extra space and merging only relinks nodes. Find the middle with a fast pointer that starts one step ahead, cut the list, sort both halves recursively and merge them. Recursion depth is log n, so the stack cost is small. Time O(n log n), space O(log n) for recursion.. Edge cases: empty or single node, duplicates, already sorted list.

    python
    def sort_list(head):
        if not head or not head.next:
            return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        mid, slow.next = slow.next, None
        a, b = sort_list(head), sort_list(mid)
        dummy = tail = ListNode()
        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
    java
    import java.util.*;
    
    class Solution {
        static ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode slow = head, fast = head.next;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode mid = slow.next;
            slow.next = null;
            ListNode a = sortList(head), b = sortList(mid);
            ListNode dummy = new ListNode(0), tail = dummy;
            while (a != null && b != null) {
                if (a.val <= b.val) { tail.next = a; a = a.next; }
                else { tail.next = b; b = b.next; }
                tail = tail.next;
            }
            tail.next = a != null ? a : b;
            return dummy.next;
        }
    }
  9. 9

    Reverse nodes in groups of k; leave a final short group unchanged.

    hard

    Use a dummy node and a group_prev pointer before each group. Walk k steps to find the group end; if fewer than k nodes remain, stop. Reverse the nodes between group_prev and the node after the group end, with the first reversed pointer aimed at that next node. Then reconnect: group_prev.next becomes the group end, and the old first node becomes the next group_prev. Time O(n), space O(1).. Edge cases: k = 1 (unchanged), k equal to the length, length not divisible by k.

    python
    def reverse_k_group(head, k):
        dummy = ListNode(0, head)
        group_prev = dummy
        while True:
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next
            group_next = kth.next
            prev, cur = group_next, group_prev.next
            while cur is not group_next:
                cur.next, prev, cur = prev, cur, cur.next
            first = group_prev.next
            group_prev.next = kth
            group_prev = first
    java
    import java.util.*;
    
    class Solution {
        static ListNode reverseKGroup(ListNode head, int k) {
            ListNode dummy = new ListNode(0, head), groupPrev = dummy;
            while (true) {
                ListNode kth = groupPrev;
                for (int i = 0; i < k; i++) {
                    kth = kth.next;
                    if (kth == null) return dummy.next;
                }
                ListNode groupNext = kth.next, prev = groupNext, cur = groupPrev.next;
                while (cur != groupNext) {
                    ListNode nxt = cur.next;
                    cur.next = prev;
                    prev = cur;
                    cur = nxt;
                }
                ListNode first = groupPrev.next;
                groupPrev.next = kth;
                groupPrev = first;
            }
        }
    }
  10. 10

    Merge k sorted linked lists.

    hard

    Keep a min-heap holding the current head of each list. Pop the smallest node, append it to the result and push that node next, if any. The heap never holds more than k nodes, so each of the N total nodes costs O(log k). In Python include an index in the tuple so ties never compare nodes. Time O(N log k), space O(k).. Edge cases: empty input array, some lists empty, a single list.

    python
    import heapq
    
    def merge_k_lists(lists):
        heap = [(l.val, i, l) for i, l in enumerate(lists) if l]
        heapq.heapify(heap)
        dummy = tail = ListNode()
        while heap:
            _, i, node = heapq.heappop(heap)
            tail.next = node
            tail = node
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next
    java
    import java.util.*;
    
    class Solution {
        static ListNode mergeKLists(ListNode[] lists) {
            PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
            for (ListNode l : lists) if (l != null) pq.add(l);
            ListNode dummy = new ListNode(0), tail = dummy;
            while (!pq.isEmpty()) {
                ListNode node = pq.poll();
                tail.next = node;
                tail = node;
                if (node.next != null) pq.add(node.next);
            }
            return dummy.next;
        }
    }

Frequently asked questions

Why use a dummy node in linked list problems?

It gives the head a predecessor, so deleting or inserting at the front uses the same code as any other position. It removes a whole class of null checks.

What is the most common linked list bug?

Overwriting a pointer before saving it, which loses the rest of the list. Save next first, then relink. The second most common is forgetting to null-terminate a split list.

Can I reverse a list recursively?

Yes: reverse the rest, then point the next node back at the current one and set current.next to null. It uses O(n) stack space, so mention the iterative version for long lists.

Array or linked list: which is faster?

Arrays have O(1) random access and better cache locality. Linked lists give O(1) insert or delete at a known node. In interviews, state both costs before choosing.

Where do cycles and the middle node fit in?

They are the fast and slow pointer pattern. See fast and slow pointers questions and stack questions for list-adjacent problems.

Related guides

More in DSA Interview Questions

See all in this section