Problem statement:
You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure.
Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.
Input format:
Linked list by giving the head node
Output format:
Return head of flattened linked list
Sample Input 1: head=[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Sample Output 1: head=[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Sample Input 2: head = [1,2,null,3]
Sample Output 2: [1,3,2]
Constraints:
- The number of Nodes will not exceed 1000.
- 1 <= Node.val <= 10⁵
Approach:
Our main aim is to make a single list in sorted order of all nodes. We will recurse until the head pointer moves null. The main motive is to merge each list from the last. Create a dummy node. Point two pointers, i.e, temp and res on dummy node. res is to keep track of dummy node and temp pointer is to move ahead as we build the flattened list. We iterate through the two chosen. Move head from any of the chosen lists ahead whose current pointed node is smaller. Return the new flattened list found.
We will assign individual lists with bottom pointers names as l1, l2, l3, and l4 respectively for our convenience. The merge function works like the merge algorithm of merge sort. Firstly, the algorithm will merge l3,l4 lists. The same way other pairs of lists will be merged.
Time complexity: O(n)
Space complexity: O(1)
Code:
Thanks for Reading
Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.
Learn more at Placewit. Follow us on Instagram and Facebook for daily learning
