Question 1

Iterative reversal of a singly linked list. Which body is correct?prev, cur = None, head
while cur:
 # body
return prev

Accepted Answer

nxt = cur.next; cur.next = prev; prev = cur; cur = nxt Save next before overwriting it, then link back and advance. Overwriting cur.next first makes cur = cur.next jump to prev and loses the rest. Setting prev before relinking makes cur point to itself. The last option also links cur to itself because prev was already moved.

Question 2

Detect a cycle in O(1) space. Which is right?

Accepted Answer

Fast moves two, slow moves one; a cycle exists if they meet Floyd's tortoise and hare meets inside any cycle and uses O(1) space. Mutating values corrupts input and fails if None is a valid value. A step cap is a guess tied to constraints. A visited set is correct but O(n) space.

Question 3

Remove the nth node from the end in one pass, where n can equal the list length. What avoids a special case for removing the head?

Accepted Answer

A dummy node before head, with both pointers starting at it With a dummy, the slow pointer lands on the node before the target even when the target is the head. Starting at head needs a separate branch for n equal to length. Reversing is extra passes and still has edge cases. Length then walk is two passes, not one.

Question 4

Merge two sorted lists of lengths m and n. What is the time and extra space of the iterative merge?

Accepted Answer

O(m + n) time, O(1) extra space Relinking existing nodes behind a dummy needs only pointers. Extra O(m + n) space is the recursive version's stack or copying into new nodes. O(m n) is inserting each node by scanning. Sorting the union adds an unnecessary log factor.

Question 5

Middle of the Linked List: return the second middle when length is even. Loop: while fast and fast.next: slow, fast = slow.next, fast.next.next. Both start at head. What does it return for 1->2->3->4?

Accepted Answer

Node 3 For 4 nodes, slow moves twice to node 3, which is the second middle. Node 2 is what you get if fast starts at head.next. Node 4 is the tail. The guard checks fast.next before reading fast.next.next, so nothing raises.

Question 6

Reorder List L0, Ln, L1, Ln-1 in place with O(1) extra space. Approach?

Accepted Answer

Find the middle with slow and fast, reverse the second half, then merge the two halves alternately. Cut the first half at the middle to avoid a cycle. O(n) time, O(1) space.

Linked list coding interview questions

More coding topics

Practise these on your commute