Good morning software developers and software engineers! Hope your day has started on the right note. Every morning, weather allowing for it, my wife and I have breakfast and go for a brisk walk. Today was no exception. Before 08:00 AM I have watered plants in the yard including a rosemary bush that we planted a week ago or so, showered, shaved, got dressed and started my work day. It is amazing how well you feed during the day once you have exercised, no matter how short or long.
Last week I read the article (let me see if I can find it in my Twitter account @john_canessa … found it) Cybersecurity bills gain new urgency after rash of attacks. It seems that both political parties, Democrats and Republicans are pushing a bill that will help our country against cyber attacks. In the past few months we have seen hundreds if not thousands of attacks, some to disable our government, companies and organizations or to ask for ransom. One of the proposed ideas is to force targets to disclose in a short period of time (24 hours or so) any cyber breach they have experienced. This will allow the government and other organizations to take action as needed to prevent the same type of attacks. In my opinion there should be some type of penalty for the bad actors in an attempt to curb their proliferation (transparency and accountability). Will see what happens with the bill and its implementation!
The main subject for this post is LeetCode 430 Flatten a Multilevel Doubly Linked List problem. Earlier this year, we solved a similar problem, which you can find in this blog under Flatten a Linked List in Java.
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. Constraints: o The number of Nodes will not exceed 1000. o 1 <= Node.val <= 105
The idea is that we are given a doubly linked list in which nodes have a third element named `child`. Some nodes may have a reference to a different linked list. The process may go on a few times.
Our task, if we accept this challenge, is to coalesce all linked lists into a single one. Each list should be incorporated / patched after the node holding the `child` link.
We are going to attempt to solve the problem using the Java programming language and the VSCode IDE on a Windows computer. Due to this approach we will also have to develop a test scaffold to read the input data, generate the multilevel linked list, call the function of interest and display the results. If this is not appealing to you, the best approach is to directly use the on-line IDE provided by LeetCode.
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
};
*/
class Solution {
public Node flatten(Node head) {
}
We have to develop the linked list using the provided Node class. The signature of the function of interest is presented with a single argument which is the head of the multilevel doubly linked list we need to flatten.
1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12 main <<< arr: [1, 2, 3, 4, 5, 6, null, null, null, 7, 8, 9, 10, null, null, 11, 12] main <<< head: (1)->(2)->(3)->(7)->(8)->(11)->(12)->(9)->(10)->(4)->(5)->(6) 1,2,null,3 main <<< arr: [1, 2, null, 3] main <<< head: (1)->(3)->(2) 1 main <<< arr: [1] main <<< head: (1) main <<< arr: null main <<< head: 1,null,2,null,3,null main <<< arr: [1, null, 2, null, 3, null] main <<< head: (1)->(2)->(3)
We are provided with a single input line. In the first test case there are three different linked lists. The first one starts at the head. The second starts at node 3, and the third at node 8. If interested, LeetCode provides a nice diagram of this linked list.
Our test code seems to read the input line and assign it to an Integer[] array. The array is then displayed to allow us to check if all is well so far. The function of interest is then called and the results are displayed.
Our test cases display a single result, but we have two implementations. The first does not use recursion. The second does.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
Integer[] arr = null;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// ???? does not support null values ????
// Integer[] arr = Arrays.stream(br.readLine().trim().split(","))
// .mapToInt(Integer::parseInt)
// .boxed()
// .toArray(Integer[]::new);
// ???? supports null values ????
// Integer[] arr = Arrays.stream(br.readLine().trim().split(","))
// // .mapToInt(x -> ((x == null) ? (Integer)null : Integer.parseInt(x)))
// .map( x -> ((x == null) ? (Integer)null : Integer.parseInt(x)) )
// // .boxed()
// .toArray(Integer[]::new);
// **** populate String[] with input values ****
String[] strs = br.readLine().trim().split(",");
// ???? ????
// System.out.println("main <<< strs.length: " + strs.length);
// for (int i = 0; i < strs.length; i++)
// System.out.println("main <<< strs[" + i + "] ==>" + strs[i] + "<==");
// **** allocate and populate arr ****
if (!(strs.length == 1 && strs[0].equals(""))) {
// **** allocate arr ****
arr = new Integer[strs.length];
// **** populate arr ****
for (int i = 0; i < arr.length; i++) {
if (strs[i].equals("null"))
arr[i] = null;
else
arr[i] = Integer.parseInt(strs[i]);
}
}
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** create and populate multilevel doubly linked list ****
Node head = buildLinkedList(arr);
// // **** flatten the linked list ****
// head = flatten0(head);
// // **** display flatten linked list ****
// System.out.print("main <<< head: "); forward(head);
// **** flatten the linked list ****
head = flatten(head);
// **** display flatten linked list ****
System.out.print("main <<< head: "); forward(head);
}
Our test code, which is NOT PART OF THE SOLUTION, reads the input line and populates an Integer[] array as was described while looking at the test cases.
If needed, multiple additional linked lists are created, populated and attached to the specified node in the main linked list. This is done by the `buildLinkedList` function which takes as an argument the `arr`.
The first attempt, which was accepted by LeetCode, has been commented out. We will look at this code shortly.
The second attempt, which was also accepted by LeetCode, uses recursion. We will also take a look at it in a few.
/**
* Build multilevel dobly linked list.
*
* !!! NOT PART OF SOLUTION !!!!
*/
static Node buildLinkedList (Integer[] arr) {
// **** sanity checks ****
if (arr == null) return null;
// **** initialization ****
Node head = null;
Node h = null;
Node t = null;
Node n = null;
// **** process the array creating the linked list ****
for (int i = 0; i < arr.length; i++) {
// **** process integer ****
if (arr[i] != null) {
// **** create node and set value ****
Node node = new Node();
node.val = arr[i];
// **** ****
if (n != null) {
n.child = node;
n = null;
h = null;
t = null;
}
// **** this node is a head ****
if (h == null) {
// **** set head and tail of queue ****
if (head == null) {
head = node;
}
// **** set head and tail of this linked list ****
h = node;
t = node;
}
// **** this node is not a head ****
else {
// **** update next on previous node ****
t.next = node;
// **** update node links ****
node.prev = t;
// **** update tail ****
t = node;
}
}
// **** process null ****
else {
// **** first n ****
if (n == null)
n = h;
// **** next n ****
else
n = n.next;
}
}
// **** return head ****
return head;
}
This is the code we used to build the multilevel doubly linked list. I will not elaborate on it at this time given that this code is NOT PART OF THE SOLUTION.
/**
* Traverse linked list forward (head -> tail).
*
* !!! NOT PART OF SOLUTION !!!
*/
static void forward(Node head) {
// **** display all nodes in the linked list ****
for (Node p = head; p != null; p = p.next) {
System.out.print(p.toString());
if (p.next != null)
System.out.print("->");
}
// **** end of linked list ****
System.out.println();
}
When I deal with different data structures, I typically like to display their contents while I develop the code, or to display the final result. This function displays a linked list from head to tail.
/**
* Traverse linked list backwards (head <- tail).
*
* !!! NOT PART OF SOLUTION !!!
*/
static void backward(Node tail) {
// **** display all nodes in the linked list ****
for (Node p = tail; p != null; p = p.prev) {
System.out.print(p.toString());
if (p.prev != null)
System.out.print("->");
}
// **** start of linked list ****
System.out.println();
}
This function displays a linked list from tail to head. We could have generated a single function that displays the values and checks the links instead of displaying the linked list in two directions. I have been using the first approach and seem to do the job. One of these days I will implement the second approach.
/**
* 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.
*
* Runtime: 1 ms, faster than 17.76% of Java online submissions.
* Memory Usage: 37 MB, less than 58.65% of Java online submissions.
*/
static Node flatten0(Node head) {
// **** traverse main list until end ****
for (Node p = head; p != null; p = p.next) {
// **** check if this node has a child list ****
if (p.child != null) {
// **** ****
Node child = p.child;
// **** to avoid endless loop ****
p.child = null;
// **** ****
child = flatten0(child);
// **** set `t` to tail in child linked list ****
Node t = child;
for ( ; t.next != null; t = t.next);
// **** splice child linked list AFTER `p` node ****
t.next = p.next;
if (p.next != null)
p.next.prev = t;
p.next = child;
child.prev = p;
}
}
// **** return head node of list ****
return head;
}
This was my first approach. It is recursive since it calls itself at the start of each linked list. The taks of attaching the linked list to the original one is done in the previous recursive call.
When all is said and done we return the linked list.
/**
* 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.
*
* 26 / 26 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 38.3 MB
*/
static Node flatten(Node head) {
// **** flatten list (recursively) ****
flattenRecursive(head);
// **** return head node ****
return head;
}
In this approach, we start by calling a method that recursively flattens the linked list. When all is said and done we return the resulting linked list. This implementation seems to be cleaner than the previous one, yet both achieve the same results.
/**
* Recursive call.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.3 MB, less than 25.33% of Java online submissions.
*
* O(n)
*/
static private Node flattenRecursive(Node head) {
// **** end condition ****
if (head == null || (head.next == null && head.child == null)) return head;
// **** recursive calls ****
Node ct = flattenRecursive(head.child);
Node nt = flattenRecursive(head.next);
// **** ****
if (ct != null) {
if (nt != null) {
// **** link after flatten child list ****
ct.next = head.next;
head.next.prev = ct;
ct = nt;
}
// **** link flatten child list ****
head.next = head.child;
head.next.prev = head;
head.child = null;
// **** return child tail ****
return ct;
} else {
// **** return next tail ****
return nt;
}
}
This function starts by checking the base case. It then makes a couple recursive calls.
The first uses head child node which in most cases is set to null. The second uses the next node in the current linked list.
Base on the results we patch the linked lists as needed.
As you should be able to tell the approach performs the same tasks with different implementations. Note that the execution times may be found in the comment section of both implementations. The second approach is 1 ms faster.
I enjoy experimenting and working with linked lists. As a matter of fact one of the `guardrails` that I have developed some time ago in the form of a DLL is based on a queue implemented as a doubly linked list. Currently the DLL named sncrque.dll holds 60+ functions.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John