Doubly Linked Lists.
This time, let’s try Doubly Linked Lists which may sound a little challenging when compared to the last ones, but it’s actually not that much.
Since we have seen the Linked list for the last couple of weeks, let’s get deeper into the subject. This time, we have both prev and next pointers, which are known as Doubly Linked Lists.
When you look at image 02, it might be easier for you to visualize it.
Just to make sure, the beginning and the end of the Linked List points at NULL.
Question:
Given a doubly linked list, list nodes also have a child property that can point to a separate doubly linked list.
These child lists can also have one or more child doubly linked lists of their own, and so on.
Return the list as a single-level flattered doubly linked list.
Explanation:
So, what the question is asking us is that in the case of a node that has a child node below it, reorganize the whole list and return it.
In other cases, the child node could be null.
And we wouldn’t know which node has how many child nodes.
Maybe it could be another node has a child.
Sample 1:
So, if we get this linked lists that has children nodes below it…
Just return it in this form, and this process is called flattening.
Sample 2:
And in another case, a child node has its grandchild node.
And in such cases, there are several ways to solve this problem. First, move grandchild F up to the child node lits.
And then, move the child-linked list to the parent-linked list.
Or… make the parent-linked list absorb the child-linked list.
And then, make the child-linked list to absorb the grandchild-linked list.
Ultimately, it might look like this.
For the record, in other cases, it might look like this – a tree-branching form that has multiple child/grandchild branches.
Coding solution:
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
}
class Solution {
public Node flatten(Node head) {
// case where [] is the input :
if (head == null) {
return head;
}
Node current = head, childNode = null;
// Traverse the pointers to get current parentNode and the tail of the childNode
while (current != null) {
if (current.child != null) {
childNode = current.child;
while (childNode.next != null) {
childNode = childNode.next; // childNode will point to the tail of the list
}
// reorg the pointers
// this check is done in case the current child is in the tail // of the current parent node.
if (current.next != null) {
childNode.next = current.next;
current.next.prev = childNode;
}
current.child.prev = current;
current.next = current.child;
current.child = null;
}
current = current.next;
}
return head;
}
}
public class Main {
public static void main(String[] args) {
// Create sample linked nodes
Node head = new Node();
head.val = 1;
Node node2 = new Node();
node2.val = 2;
Node node3 = new Node();
node3.val = 3;
Node node4 = new Node();
node4.val = 4;
Node node5 = new Node();
node5.val = 5;
Node node6 = new Node();
node6.val = 6;
Node node7 = new Node();
node7.val = 7;
Node node8 = new Node();
node8.val = 8;
Node node9 = new Node();
node9.val = 9;
Node node10 = new Node();
node10.val = 10;
Node node11 = new Node();
node11.val = 11;
Node node12 = new Node();
node12.val = 12;
// Link the nodes with children
head.next = node2;
node2.prev = head;
node2.next = node3;
node3.prev = node2;
node3.next = node4;
node4.prev = node3;
node4.next = node5;
node5.prev = node4;
node5.next = node6;
node6.prev = node5;
node3.child = node7;
node7.next = node8;
node8.prev = node7;
node8.next = node9;
node9.prev = node8;
node9.child = node10;
node10.next = node11;
node11.prev = node10;
node11.next = node12;
node12.prev = node11;
// Flatten the linked list
Solution solution = new Solution();
Node flattened = solution.flatten(head);
// Print the flattened list
while (flattened != null) {
System.out.print(flattened.val + " ");
flattened = flattened.next;
}
}
}
Step-by-step description:
The Node class is defined, which has four instance variables: val, prev, next, and child. These variables represent the value of the node, the previous and next nodes in the doubly linked list, and the child node (if any) of the current node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
}The flatten method is defined in the Solution class, which takes a head node of the doubly linked list as input and returns the flattened linked list.
class Solution {
public Node flatten(Node head) {
// case where [] is the input :
if (head == null) {
return head;
}
Node current = head, childNode = null;
// Traverse the pointers to get current parentNode and the tail of the childNode
while (current != null) {
if (current.child != null) {
childNode = current.child;
while (childNode.next != null) {
childNode = childNode.next; // childNode will point to the tail of the list
}
// reorg the pointers
// this check is done in case the current child is in the tail // of the current parent node.
if (current.next != null) {
childNode.next = current.next;
current.next.prev = childNode;
}
current.child.prev = current;
current.next = current.child;
current.child = null;
}
current = current.next;
}
return head;
}
}If the input head is null, which means the linked list is empty, the method simply returns the input head.
if (head == null) {
return head;
}Otherwise, two pointers current and childNode are initialized to head and null, respectively. These pointers will be used to traverse the doubly linked list and its children.
Node current = head, childNode = null;A while loop is used to traverse the doubly linked list. Inside the loop, the code checks whether the current node has a child node. If so, the childNode pointer is set to the child node of the current node, and another while loop is used to traverse the child nodes until the tail node is found.
while (current != null) {
if (current.child != null) {
childNode = current.child;
while (childNode.next != null) {
childNode = childNode.next; // childNode will point to the tail of the list
}Once the tail node of the child nodes is found, the pointers are reorganized to flatten the child nodes into the parent node. Specifically, the next pointer of the tail node is set to the next node of the current node (if any) and the prev pointer of the next node (if any) is set to the tail node. Then, the prev pointer of the child node is set to the current node, the next pointer of the current node is set to the child node, and the child pointer of the current node is set to null. This effectively flattens the child nodes into the parent node.
if (current.next != null) {
childNode.next = current.next;
current.next.prev = childNode;
}After the pointers have been reorganized, the current pointer is moved to the next node in the doubly linked list.
Once the end of the doubly linked list is reached, the method returns the head node.
current.child.prev = current;
current.next = current.child;
current.child = null;
}
current = current.next;
}
return head;In the main method, a sample doubly linked list is created with 12 nodes and children nodes.
The head node is passed to the flatten method to flatten the linked list.
The flattened linked list is printed to the console.
Output result:
1 2 3 7 8 9 10 11 12 4 5 6