Package g0401_0500.s0430_flatten_a_multilevel_doubly_linked_list

Class Node

java.lang.Object
g0401_0500.s0430_flatten_a_multilevel_doubly_linked_list.Node
public class Node extends Object
430 - Flatten a Multilevel Doubly Linked List.<p>Medium</p> <p>You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional <strong>child pointer</strong>. 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 <strong>multilevel data structure</strong> as shown in the example below.</p> <p>Given the <code>head</code> of the first level of the list, <strong>flatten</strong> the list so that all the nodes appear in a single-level, doubly linked list. Let <code>curr</code> be a node with a child list. The nodes in the child list should appear <strong>after</strong> <code>curr</code> and <strong>before</strong> <code>curr.next</code> in the flattened list.</p> <p>Return <em>the</em> <code>head</code> <em>of the flattened list. The nodes in the list must have <strong>all</strong> of their child pointers set to</em> <code>null</code>.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/11/09/flatten11.jpg" alt="" /></p> <p><strong>Input:</strong> head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]</p> <p><strong>Output:</strong> [1,2,3,7,8,11,12,9,10,4,5,6]</p> <p><strong>Explanation:</strong> The multilevel linked list in the input is shown. After flattening the multilevel linked list it becomes: <img src="https://assets.leetcode.com/uploads/2021/11/09/flatten12.jpg" alt="" /></p> <p><strong>Example 2:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/11/09/flatten2.1jpg" alt="" /></p> <p><strong>Input:</strong> head = [1,2,null,3]</p> <p><strong>Output:</strong> [1,3,2]</p> <p><strong>Explanation:</strong></p> <pre><code> The multilevel linked list in the input is shown. After flattening the multilevel linked list it becomes: </code></pre> <p><img src="https://assets.leetcode.com/uploads/2021/11/24/list.jpg" alt="" /></p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> head = []</p> <p><strong>Output:</strong> []</p> <p><strong>Explanation:</strong> There could be empty list in the input.</p> <p><strong>Constraints:</strong></p> <ul> <li>The number of Nodes will not exceed <code>1000</code>.</li> <li><code>1 <= Node.val <= 10<sup>5</sup></code></li> </ul> <p><strong>How the multilevel linked list is represented in test cases:</strong></p> <p>We use the multilevel linked list from <strong>Example 1</strong> above:</p> <pre><code> 1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULL </code></pre> <p>The serialization of each level is as follows:</p> <pre><code> [1,2,3,4,5,6,null] [7,8,9,10,null] [11,12,null] </code></pre> <p>To serialize all levels together, we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:</p> <pre><code> [1, 2, 3, 4, 5, 6, null] | [null, null, 7, 8, 9, 10, null] | [ null, 11, 12, null] </code></pre> <p>Merging the serialization of each level and removing trailing nulls we obtain:</p> <pre><code> [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] </code></pre>

  • Field Details

    • val

      public int val

    • prev

      public Node prev

    • next

      public Node next

    • child

      public Node child

  • Constructor Details

    • Node

      public Node(int val)

  • Method Details