This question is asked very commonly at Bloomberg. Here is the question:
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 separate double linked lists. These child lists may have one of more children on their own and so on to produce a multilevel data structure. It's like trees and children in hierarchy, and we want to flatten a list. You definitely run DFS here, and I want to do it through iteration this time, just to get experience in both perspectives.
And here's how the list will be represented:
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL
and the level starts as
[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
and the serialization becomes the following:
[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]
Notice, the 7 is after the SECOND index, and the 11 is after the FIRST index, and the output would be equal to:
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12].
And the constraints are:
The number of Nodes will not exceed 1000.
1 <= Node.val <= 10^5.
Now time for the depth-first-search solution, and I will go over both of them here. This data structure can be used very commonly in git branching. We can think about this as merging all the git branches together.
We can distinguish nodes with different colors and flatten the list in several recursive steps. Here's an example. This is also a solution in the top 0.1% of solutions on Leetcode. This is basically a DFS traversal over a binary tree.
I will hereby describe the first algorithm below. We want to perform a preorder depth first search, and we define a recursive function which takes 2 pointers as input and returns the pointer to the flattened list tail.
First, establish double links between the previous and current nodes, and then flatten the left subtree, and then flatten the right subtree, denoted by curr.child and curr.next, respectively.
Here's the algorithm:
class Solution {
public node flatten(Node head) {
if(head == null) return head;
//make sure that the previous pointer is never none
Node pseudoHead = new Node(0, null, head, null);
flattenDFS(pseudoHead, head);
//detach the pseudo head from the real head.
pseudoHead.next.prev = null;
return pseudoHead.next();
}
public Node flattenDFS(Node prev, Node curr) {
if(curr == null) return prev;
//set the 2 corresponding nodes as relation for one another.
curr.prev = prev;
prev.next = next;
//curr.next will be in a recursive function as well as the child.
node tempNext = curr.next;
Node tail = flattenDFS(curr, curr.child);
//nullify the child
curr.child = null;
return flattenDFS(tail, tempNext);
}
}
The time and space complexity is O(n).
The next solution that I want to describe is depth-first search by iteration, in which the key is to use a data structure called a stack, operating through the Last In First Out Principle. This also mimics recursion, and I will denote the algorithm below.
First, create a stack and push the head node to the stack, and create a prev variable to track the previous node at each step during the iteration. We first pop out a node from the stack and establish the linkes, then take care of the nodes pointed by the .next and .child pointers. If curr.next exist, we push the node to the stack, if curr.child exist, we push this into the stack, and we need to clean up this pointer
Here's the code:
class Solution {
public Node flatten (Node head) {
if(head == null) return head;
Node pseudoHead = new Node(0, null, head, null);
Node curr, prev = pseudoHead;
Deque<Node> stack = new ArrayDeque<>();
//get the first element first.
stack push(head);
//iterate through the stack
while(!stack.isEmpty()) {
//recursively get the first stack pointers so that the nested children come first, then the .next nodes
cur = stack.pop();
//iterate previous in the pseudohead.
prev.next = curr;
curr.prev = prev;
if(curr.next != null) stack.push(curr.next);
if(curr.child != null)
stack.push(curr.child);
curr.child = null;
prev = curr;
}
//remove the original head
pseudoHead.next.prev = null;
//this is the new head.
return pseudoHead.next;
}
}
This solution is also denoted as O(N) So flatten the child first, then set the .child to null, then flatten the next one.
Comments
Post a Comment