Medium · Linked Lists

Flatten doubly linked list

Given a multilevel doubly linked list as a node table (nodes[i] = {val, next, child}, with indices and −1 for none; node 0 is the head), where any node may point to the head of a child list, flatten it in place into one doubly linked level in which every child list appears right after its parent and before the parent's original next node; set every child pointer to null and return the head.

Examples

Example 1

{
  "nodes": [
    {"val": 1, "next": 1, "child": -1},
    {"val": 2, "next": 2, "child": 4},
    {"val": 3, "next": 3, "child": -1},
    {"val": 4, "next": -1, "child": -1},
    {"val": 7, "next": 5, "child": -1},
    {"val": 8, "next": 6, "child": -1},
    {"val": 9, "next": -1, "child": -1}
  ]
}

Output: 1 2 7 8 9 3 4

Example 2

{
  "nodes": [
    {"val": 1, "next": 1, "child": -1},
    {"val": 2, "next": 2, "child": 3},
    {"val": 3, "next": -1, "child": -1},
    {"val": 4, "next": -1, "child": 4},
    {"val": 5, "next": -1, "child": -1}
  ]
}

Output: 1 2 4 5 3

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.