Flattening of LL

New·#430·Hard·Linked List

Flatten a multi-level linked list with child and next pointers by recursively merging them in place

Asked at:AmazonMicrosoftGoldman Sachs

Practice mode

Step

Original Multi-Level List

A list with 4 main nodes, each having a child sub-chain.

Cache workspace

Recursive Merge

Step 1 / 8init

100%

Main node 5 child chain

→

→null

Main node 10 child chain

→

→null

Main node 12 child chain

→

→null

Main node 7 child chain

→

→null

Explanation

The original list contains next pointers going right, and child pointers going down. To flatten, we recursively merge the rightmost chains together first.

step 1 / 8

Space play← → stepHome reset

TimeO(n * m)·SpaceO(n)

Recursive Merge

1class Solution {
2    merge(list1, list2) {
3        let dummyNode = new ListNode(-1);
4        let res = dummyNode;
5 
6        while (list1 !== null && list2 !== null) {
7            if (list1.val < list2.val) {
8                res.child = list1;
9                res = list1;
10                list1 = list1.child;
11            } else {
12                res.child = list2;
13                res = list2;
14                list2 = list2.child;
15            }
16            res.next = null;
17        }
18 
19        if (list1 !== null) {
20            res.child = list1;
21        } else {
22            res.child = list2;
23        }
24 
25        if (dummyNode.child !== null) {
26            dummyNode.child.next = null;
27        }
28 
29        return dummyNode.child;
30    }
31 
32    flattenLinkedList(head) {
33        if (head === null || head.next === null) {
34            return head;
35        }
36 
37        let mergedHead = this.flattenLinkedList(head.next);
38        head = this.merge(head, mergedHead);
39        return head;
40    }
41}

Command Palette

Flattening of LL

Flattening of LL