LeetCode #430 Flatten a Multilevel Doubly Linked List
Problem
You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.
Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.
Example:
Input:
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULLOutput:
1-2-3-7-8-11-12-9-10-4-5-6-NULL
Explanation for the above example:
Given the following multilevel doubly linked list:
We should return the following flattened doubly linked list:
Solution
One may found that every child list can be seen as a list which should be flatten, which means this problem can be solved by recursion. Therefore, we can use a pointer to find one node which contains child and call flatten function on both rest list and child list. It’s noted that we need to traverse child list for tail after flattened.
Complexity
Although we use recursion in this approach, it’s still easy to find out that we only visit each node once in this list, which costs O(n) time if n denotes to amount of nodes in entire list, except finding child tail of each child list. For finding child tail, it will traverse each child list which means it will cost less time than visit all nodes in this list. So it also takes O(n) time. Therefore, total time complexity is O(n+n) = O(n).
For space complexity, each child pointer cause two recursion and it uses O(1) extra space in each recursion. Hence it will costs O(2k) = O(k) extra space if k denotes to counts of nodes that have child in this list, and it’s clear that k will be less than n. So space complexity is O(n) as well.
