Flatten a Multilevel Doubly Linked List
Medium Doubly linked list splicing
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A doubly linked list's nodes may have a child pointer to another doubly linked list (which may have children too). Flatten everything into one level, placing each child list right after its parent node.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: splice every child list in right after its parent node.
Why this works: on a node with a child, link node ⇄ child, find the child list's tail, link tail ⇄ old next, and clear the child pointer.
Example: 1 ⇄ 2 ⇄ 3, where 2 has child 7 ⇄ 8
1 ⇄ 2 ⇄ 7 ⇄ 8 ⇄ 3✦Hints open one at a time
↗Approach
Walk the list. On a node with a child: remember next, link node ↔ child, walk to the child list's tail, link tail ↔ next, and clear the child pointer. Continue walking — nested children are handled when reached.
</>Solution (Java)
/*
* class Node { int val; Node prev; Node next; Node child; } // provided by LeetCode
*/
class Solution {
public Node flatten(Node head) {
for (Node cur = head; cur != null; cur = cur.next) {
if (cur.child == null) continue;
Node next = cur.next, child = cur.child;
cur.next = child;
child.prev = cur;
cur.child = null;
Node tail = child;
while (tail.next != null) tail = tail.next; // end of the child list
tail.next = next;
if (next != null) next.prev = tail;
}
return head;
}
}!Common mistake
Forgetting the prev pointers or leaving child non-null — the judge checks both.
- Time: O(n).
- Space: O(1).