Skip to content
Tech Interview Prep
Technical interview guide

Linked Lists

Singly/doubly linked lists, pointer manipulation, and the classic two-pointer patterns.

Read
40 min
Practice MCQs
25
Interview Q&A
25
Edition
v6
Editorial status
Reviewed

Scope: Language-neutral, with container behaviour cited from CPython 3.14, the C++ standard containers, and java.util as of Java 21.

Curated: · Written: · Reviewed:

25 questions

MCQ-12When merging two sorted singly linked lists of lengths m and n in-place, what are the optimal time and auxiliary space complexities?
MCQ-3A team is implementing deletion of a node by value and merging two sorted singly linked lists, and wants one code path that handles removing the first element and merging into an empty result. Why does a dummy (sentinel) head node remove those special cases?
MCQ-4A candidate writes this function (Python 3) to reverse a singly linked list and calls it with `head` pointing to `1 → 2 → 3 → 4`: ```python def reverse(head): prev, node = None, head while node: node.next = prev nxt = node.next prev, node = node, nxt return prev ``` What does the call return?
MCQ-22A singly linked list of five nodes is `1 -> 2 -> 3 -> 4 -> 5 -> None`. A function `reverse_in_place(head)` relinks those existing nodes so the list becomes `5 -> 4 -> 3 -> 2 -> 1 -> None`, then returns the new head. A caller runs: ```python old = head new = reverse_in_place(head) print(count_nodes(old)) ``` where `count_nodes(node)` counts nodes reachable from `node` by following `next` until `None`. What does the caller print?
MCQ-5What is the auxiliary space complexity of recursively reversing a singly linked list of length n, and what mechanism determines that cost?
MCQ-8A `middle(head)` helper walks two pointers that both start at head; the loop body is fixed as `slow = slow.next; fast = fast.next.next;` followed by `return slow`. Its contract: the middle node on odd-length lists, the second middle node on even-length lists (for `1 -> 2 -> 3 -> 4 -> null`, the node holding 3), `null` on an empty list, and no exception for any length from 0 upward. Which loop condition satisfies the whole contract?
MCQ-9A singly linked list has six nodes, `1 → 2 → 3 → 4 → 5 → 6`, and node 6's `next` points back to node 4. A `has_cycle` function starts with `slow = fast = head`, and each iteration runs `slow = slow.next; fast = fast.next.next`, comparing the two pointers after every move. Where do the pointers first coincide?
MCQ-24A cache stores its entries in a singly linked chain of 200,000 nodes. A bug in the eviction path splices the last node so it points back at the third-from-last node, forming a 3-node cycle. A nightly health check walks the chain with Floyd's tortoise-and-hare (tortoise one node per step, hare two) and raises CorruptedError the moment both pointers land on the same node. It has no step budget. What does the check do?
MCQ-10An engineer evaluates whether to detect cycles in an in-memory singly linked list using a hash set of visited node references or Floyd's tortoise and hare algorithm. Under memory-constrained profiling, which comparison of their practical performance and complexity is technically accurate?
MCQ-11Two singly linked lists share no nodes. List A holds 1 → 2 → 3 → 4 → 5 and list B holds 9 → 3 → 5. A developer implements the length-alignment intersection check but compares `a.val == b.val` instead of `a is b`: the function computes both lengths, advances the pointer on the longer list by the length difference, then walks both pointers together and returns the first node whose value equals its aligned partner's value, or None if both pointers reach the end. What does this function return?
MCQ-7A job queue is a singly linked list of nodes holding values 1→2→3→4→5, and a dict maps each job id to its node object. A worker finishes job 3 and holds only a pointer to node 3; it removes it with the value-copy trick (node.val = node.next.val; node.next = node.next.next). What is the resulting state?
MCQ-6A singly linked list holds 1 → 2 → 3 → 4 → 5. A teammate's `reverse_between(head, left, right)` is supposed to reverse the nodes from position `left` to position `right` inclusive and return the head. Their Python 3 implementation is: ```python # Node(val, next) def reverse_between(head, left, right): dummy = Node(0, head) before = dummy for _ in range(left): before = before.next prev, cur = None, before.next for _ in range(right - left + 1): nxt = cur.next cur.next = prev prev = cur cur = nxt before.next = prev return dummy.next ``` Called as `reverse_between(head, 2, 4)` on that list, what does it return?
MCQ-23The tests for a doubly linked list (Python 3) all pass, because they only assert the forward walk from head. A new test appends 1, 2, 3, 4, 5, keeps a reference to the node holding 3, calls remove() on that node, then walks backward from lst.tail through prev, recording every value it visits and stopping when prev is None. ```python class Node: def __init__(self, val): self.val = val self.prev = None self.next = None class List: def __init__(self): self.head = None self.tail = None def append(self, val): node = Node(val) if self.tail is None: self.head = self.tail = node else: node.prev = self.tail self.tail.next = node self.tail = node def remove(self, node): if node.prev is not None: node.prev.next = node.next else: self.head = node.next if node.next is None: self.tail = node.prev node.prev = None node.next = None ``` Which values does the backward walk record?
MCQ-16A service keeps its LRU eviction order in a circular doubly linked list with one sentinel node. The unlink helper is correct: it splices a node out through its neighbours, and removing the last entry leaves the sentinel pointing at itself. The eviction walk is: ```python node = sentinel.next while node is not None: evict(node) node = node.next ``` After the cache is fully drained, every entry evicted, the worker pins one core at 100% CPU and never returns. What is the cause?
MCQ-17An LRU cache with capacity 3 is implemented as a hash map to nodes of a doubly linked list. Requests arrive in this order: put(A), put(B), put(C), get(A), put(D), put(E). Which key does put(E) evict?
MCQ-15An LRU cache holds 1,000,000 entries in a doubly linked list. Each node stores key (8 B), value (8 B), prev (8 B), next (8 B). The team proposes dropping the prev pointer to save memory. The cache must evict the least-recently-used node in O(1) given only its node pointer. What is the direct consequence?
MCQ-1A memory allocator keeps its free blocks on a singly linked list: freeing pushes the block onto the head with two pointer writes, and allocation pops the head. A teammate proposes keeping the list sorted by block address so adjacent blocks can be coalesced, inserting each freed block at its sorted position. The free list holds up to 500,000 blocks and the allocator handles 300,000 frees per second. What does the proposal do to the free path?
MCQ-14A merge sort on a singly linked list overflows the stack on the four-node list 1 -> 2 -> 3 -> 4. Its split routine advances a slow pointer one node and a fast pointer two nodes per step, then returns the slow pointer as the start of the second half; it never writes to any next field. What does the split return, and why does the sort not terminate?
MCQ-13You must sort a 10-million-node singly linked list. The sort must be stable, worst-case O(n log n), and must not allocate an O(n) auxiliary array. Which line do you use?
MCQ-21A CPython 3.12 batch job validates a user-supplied linked list with a recursive walk that makes one call per node: walk(node) checks the node, then calls walk(node.next). Today's payload has 5,000 nodes, the call arrives through a handler chain that already holds 40 Python frames, sys.getrecursionlimit() returns the default, and the host has 6 GB of RAM free. The job logs RecursionError partway through the list, and nothing caps the payload length. What is happening, and what lets the walk finish every input?
MCQ-18A packet scheduler keeps every active flow on two lists at once, a per-CPU run queue and a global inactivity-timeout list, and a flow has to stay schedulable while it waits to time out. Flows are heap-allocated already, so the team replaces std::list<Flow*> with an intrusive list: one next/prev pair embedded in Flow, used by both lists. After the change, timeout sweeps reap flows that are still transmitting, and a run queue walk sometimes steps off the queue and follows the timeout list instead of stopping at the run queue tail. About 1.2M flows, roughly 900K timeout-list inserts a second. Which change fixes the corruption?
MCQ-2A matching engine holds 4,000,000 live order records of 24 bytes each (an 8-byte price, an 8-byte quantity, an 8-byte id). One team keeps them in a flat array; the other keeps each record in its own malloc'd singly linked list node, sizeof(node) = 32 bytes, and profiling of the node addresses shows that no two consecutive nodes in the walk share a 64-byte cache line. A full walk visits every record in list order and sits on the hot path; L3 is 32 MB and each pass restarts from the head, so nothing from the previous pass is left cached. Measured on this machine: streaming reads move 16 bytes per nanosecond, and a load that misses to DRAM costs about 80 ns. Which estimate of one full walk of the linked list is right?
MCQ-19A telemetry service keeps the last 48,000,000 int64 samples of a stream in memory to serve a 24-hour replay. The retained count is fixed by the replay SLA, and 512 MiB (536,870,912 bytes) is reserved for this structure. Two representations are on the table: a packed int64 buffer, with values stored back to back, and a singly linked node per sample whose struct carries one 8-byte next pointer plus the 8-byte sample, with no padding on the 64-bit target. Which conclusion should the capacity plan record?
MCQ-20A market-data handler keeps a fixed-capacity window of the last 1,000,000 trades. Each incoming trade is pushed at the tail and the oldest is dropped from the head; once per batch the handler reads `window[i]` for an arbitrary i to compute a percentile. All three operations must be O(1) at 1,000,000 elements. Which structure delivers that?
MCQ-25A session cache holds 250,000 entries in a Python `list` ordered least- to most-recently-used, with a `dict` mapping each session ID to its index in that list. Every hit runs `entry = lst.pop(idx)` then `lst.append(entry)`. At 40,000 hits/s, p99 latency has risen from 3 ms to 90 ms and one core is pinned in the memmove inside `list.pop`. Which change removes the bottleneck?