AlgoViz
HomeLinked List

Flattening of LL

Hard

Merge the sorted child lists pairwise

Problem

Given a special linked list containing n head nodes where every node in the linked list contains two pointers: ‘Next’ points to the next node in the list ‘Child’ pointer to a linked list where the current node is the head Each of these child linked lists is in sorted order and connected by a 'child' pointer. Flatten this linked list such that all nodes appear in a single sorted layer connected by the 'child' pointer and return the head of the modified list.

In simple words

Repeatedly merge two sorted vertical lists (like merge-two-lists) until a single sorted list remains.

The idea

Each node heads an already-sorted bottom list, so flattening is repeated merging of two sorted lists. Recursing to the right first and merging back means every merge combines two sorted lists, which keeps it correct and simple.

The trick

  • Merge on the bottom pointer, not next.
  • Recurse right first, then merge the current list into the flattened remainder.
  • A priority queue over the heads is the alternative.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — Values: 0.

1/2
Optimal
timeO(n*m)spaceO(1)
1// each node has next (right) and bottom (down); each bottom-list is sorted2merged = null3for each node along next:4  merged = mergeSortedByBottom(merged, node)5return merged

Input

array
[0]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = [[5,7,8],[10,20],[15,22]]
Output:
5 -> 7 -> 8 -> 10 -> 15 -> 20 -> 22
Explanation:
Merge all the bottom sub-lists into one sorted chain.

Example 2

Input:
list = [[1,3],[2]]
Output:
1 -> 2 -> 3
Explanation:
1,2,3.

Example 3

Input:
list = [[9]]
Output:
9
Explanation:
One node.

Constraints

  • n == Number of head nodes
  • 1 <= n <= 100
  • 1 <= Number of nodes in each child linked list <= 100
  • 0 <= ListNode.val <= 1000
  • All child linked lists are sorted in non-decreasing order

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.