C# || How To Flatten A Multilevel Doubly Linked List Using C#
The following is a module with functions which demonstrates how to flatten a doubly linked list using C#.
1. Flatten – Problem Statement
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 1:
Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:The multilevel linked list in the input is as follows:
After flattening the multilevel linked list it becomes:
Example 2:
Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation:The input multilevel linked list is as follows:
1---2---NULL
|
3---NULL
Example 3:
Input: head = []
Output: []
2. Flatten – Solution
The following are two solutions which demonstrates how to flatten a doubly linked list.
Iterative
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
// ============================================================================ // Author: Kenneth Perkins // Date: Oct 30, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to flatten a doubly linked list // ============================================================================ /* // Definition for a Node. public class Node { public int val; public Node prev; public Node next; public Node child; } */ public class Solution { public Node Flatten(Node head) { var current = head; var stack = new Stack<Node>(); // Loop through nodes while (current != null) { // Check to see if node has child if (current.child != null) { // If current node has a next node, save to stack // so we can reconnect it to the tail // of the child node later if (current.next != null) { stack.Push(current.next); } // Set the next node as the child, // we will now iterate down this path current.next = current.child; // Set the previous node as the current current.next.prev = current; // Set child to null current.child = null; } else if (current.next == null) { // Reconnect node at the top of the // stack to the tail child node if (stack.Count > 0) { // Set the next node as the reconnected node, // we will now iterate down this path current.next = stack.Pop(); current.next.prev = current; } } current = current.next; } return head; } }// http://programmingnotes.org/ |
Recursive
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// ============================================================================ // Author: Kenneth Perkins // Date: Oct 30, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to flatten a doubly linked list // ============================================================================ /* // Definition for a Node. public class Node { public int val; public Node prev; public Node next; public Node child; } */ public class Solution { public Node Flatten(Node head) { Flatten(head, null); return head; } private Node Flatten(Node current, Node previous) { if (current == null) { return previous; } // If previous node exists, set the next and previous values if (previous != null) { previous.next = current; current.prev = previous; } // Save the next node so we can reconnect it to the tail // of the child node later var next = current.next; // Traverse down child path. // If children exist, this returns the last child for the current node var tail = Flatten(current.child, current); // Child path has been explored, set to null current.child = null; // Reconnect the next node to the tail child node return Flatten(next, tail); } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
[1,2,3,7,8,11,12,9,10,4,5,6]
[1,3,2]
[]
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
Leave a Reply