PPractick

The problem

A log collector receives events out of order and stores them in a singly linked list; before export, the list must be sorted by value in O(n log n), ideally without copying everything into an array. Quick sort needs random access for good pivots, and heap sort needs indexing, but merge sort fits linked lists perfectly: splitting at the middle uses fast and slow pointers, and merging two sorted lists only relinks nodes, so no extra buffer is needed.

Example: 4 -> 2 -> 1 -> 3 → 1 -> 2 -> 3 -> 4.

Function signature

Node* sortList(Node* head);  // returns the head of the sorted list

Test cases

Input list	Output list	Explanation
4 -> 2 -> 1 -> 3	1 -> 2 -> 3 -> 4
-1 -> 5 -> 3 -> 4 -> 0	-1 -> 0 -> 3 -> 4 -> 5	Negative values
2 -> 2 -> 1	1 -> 2 -> 2	Duplicates (stable)
1	1
(empty)	(empty)

(Confirm: sort by relinking nodes; O(n log n) time; the code cross-checks random lists against std::sort.)

How interviewers phrase it

• "Sort a linked list in O(n log n) time" (LeetCode 148).
• "Merge two sorted linked lists" (LeetCode 21) is its core step and often asked on its own.

Clarifying questions to ask

1. Is O(n log n) required?
2. Is O(1) extra space required? (Top-down recursion uses O(log n) stack; bottom-up merge sort is O(1).)
3. Can I just copy values into an array and sort? (Usually not the intended answer.)

Follow-ups to expect

1. "Why merge sort rather than quick sort?"
2. "How do you split the list?"
3. "Why must fast start at head->next?"
4. "How do you get O(1) space?"
5. "Complexity?"

Related questions

• Reverse Pairs Hard
• Delete all occurrences of a key in DLL Hard
• Remove duplicates from sorted DLL Hard
• Reverse LL in group of given size K Hard
• Rotate a LL Hard
• Flattening of LL Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in