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.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Tools | Dummy 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.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = nextclass 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.
- Dummy head: removes the "is this the first node" special case.
- Reverse in place: prev, cur and next pointers moving together.
- Gap pointers: advance one pointer n steps first, then move both.
- Always check for an empty list and a single node.
Linked list interview questions with worked solutions: questions with worked answers
1 Reverse a singly linked list.
easyWalk 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.
pythondef reverse_list(head): prev, cur = None, head while cur: nxt = cur.next cur.next = prev prev, cur = cur, nxt return prevjavaimport 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 Merge two sorted linked lists into one sorted list.
easyCreate 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.
pythondef 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.nextjavaimport 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 Remove duplicates from a sorted linked list so each value appears once.
easyBecause 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.
pythondef 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 headjavaimport 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 Remove the nth node from the end in one pass.
mediumStart 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).
pythondef 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.nextjavaimport 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 Add two numbers stored as linked lists of digits in reverse order.
mediumThe 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.
pythondef 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.nextjavaimport 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 Copy a linked list where each node also has a random pointer to any node or null.
mediumMake 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.
pythonclass 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)javaimport 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 Reorder list: turn L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> ...
mediumFind 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.
pythondef 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, n2javaimport 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 Sort a linked list in O(n log n) time.
mediumMerge 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.
pythondef 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.nextjavaimport 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 Reverse nodes in groups of k; leave a final short group unchanged.
hardUse 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.
pythondef 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 = firstjavaimport 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 Merge k sorted linked lists.
hardKeep 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.
pythonimport 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.nextjavaimport 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
- Fast and slow pointers interview questions with solutions
- Stack interview questions with worked solutions
- Two pointers interview questions with worked solutions
- Recursion interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
More in DSA Interview Questions
- Longest Common Subsequence (LCS) Interview Questions
- Longest Increasing Subsequence (LIS) Interview Questions
- LRU Cache and Design Data Structure Interview Questions
- Math and number theory interview questions with solutions
- Matrix interview questions with worked solutions
- Merge intervals pattern questions with worked solutions
- Minimum Spanning Tree Interview Questions
- Monotonic stack interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Recursion interview questions with worked solutions
- Segment Tree Interview Questions