DSA interview question

Flatten a Linked List of Sorted Sub-Lists

Hard · Data structures · Topics: linkedlist, doubly linkedlist

The problem

A newsroom collects stories from several agencies. Each agency's stories arrive as a vertical linked list sorted by timestamp (linked by bottom), and the agencies' lists are chained together by their head nodes (linked by next). The front page needs one timeline: a single sorted list linked through bottom, with every next pointer cleared. This is "merge k sorted lists" in a linked-list costume: merge the columns pairwise, from the right, using the ordinary two-list merge.

Example: columns [5, 7, 8, 30], [10, 20], [19, 22, 50], [28, 35, 40, 45] → 5 7 8 10 19 20 22 28 30 35 40 45 50.

Function signature

Node* flatten(Node* root);  // heads linked by next, each column sorted and linked by bottom

Test cases

Input (columns)	Output (via bottom)	Explanation
`[[5, 7, 8, 30], [10, 20], [19, 22, 50], [28, 35, 40, 45]]`	`5 7 8 10 19 20 22 28 30 35 40 45 50`
`[[10, 20], [20, 30], [35]]`	`10 20 20 30 35`	Duplicates are kept
`[[1], [2], [3]]`	`1 2 3`	Only head nodes
`[[3, 4, 5]]`	`3 4 5`	One column
`[]`	`(empty)`

(Confirm: each column is sorted; the result must use bottom pointers only, with every next pointer set to nullptr.)

How interviewers phrase it

"Flatten a linked list where every node has a next and a bottom pointer and each sub-list is sorted" (GeeksforGeeks).
It is essentially "merge k sorted lists" (LeetCode 23).

Clarifying questions to ask

Is every vertical list sorted?
Should the result be linked through bottom or next?
How many columns and nodes can there be? (Affects whether a heap is worth it.)

Follow-ups to expect

"How do you merge two sorted lists?"
"Why merge from the right?"
"What's the complexity of one-by-one merging?"
"Can you do better?"
"Why clear the next pointers?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview