题目

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:

  1. Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
  2. Output: [1,2,3,7,8,11,12,9,10,4,5,6]
  3. Explanation:
  5. The multilevel linked list in the input is as follows:
  9. After flattening the multilevel linked list it becomes:

Example 2:

  1. Input: head = [1,2,null,3]
  2. Output: [1,3,2]
  3. Explanation:
  5. The input multilevel linked list is as follows:
  7.   1---2---NULL
  8.   |
  9.   3---NULL

Example 3:

  1. Input: head = []
  2. Output: []

How multilevel linked list is represented in test case:

We use the multilevel linked list from Example 1 above:

  1.  1---2---3---4---5---6--NULL
  2.          |
  3.          7---8---9---10--NULL
  4.              |
  5.              11--12--NULL

The serialization of each level is as follows:

  1. [1,2,3,4,5,6,null]
  2. [7,8,9,10,null]
  3. [11,12,null]

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:

  1. [1,2,3,4,5,6,null]
  2. [null,null,7,8,9,10,null]
  3. [null,11,12,null]

Merging the serialization of each level and removing trailing nulls we obtain:

  1. [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

Constraints:

  • Number of Nodes will not exceed 1000.
  • 1 <= Node.val <= 10^5

题意

给双向链表多加一个指针域child，指向下一层的链表。要求将给定的多层链表压平成一个链表。

思路

DFS处理，从下往上合并每一层；也可以直接用迭代从上往下合并每一层。

代码实现

Java

递归

  1. class Solution {
  2.     public Node flatten(Node head) {
  3.         dfs(head);
  4.         return head;
  5.     }
  7.       // dfs返回压平后的当前链表的尾结点
  8.     private Node dfs(Node head) {
  9.         Node p = head;
  10.         Node last = null;
  11.         while (p != null) {
  12.             if (p.next == null) {
  13.                 last = p;
  14.             }
  15.             if (p.child != null) {
  16.                 Node childLast = dfs(p.child);
  17.                 Node next = p.next;
  18.                 p.next = p.child;
  19.                 p.child.prev = p;
  20.                 p.child = null;
  21.                 childLast.next = next;
  22.                 if (next != null) {
  23.                     next.prev = childLast;
  24.                 }
  25.                 p = childLast;
  26.             } else {
  27.                 p = p.next;
  28.             }
  29.         }
  30.         return last;
  31.     }
  32. }

迭代

  1. class Solution {
  2.     public Node flatten(Node head) {
  3.         Node p = head;
  4.         while (p != null) {
  5.             Node next = p.next;
  6.             if (p.child != null) {
  7.                 Node q = p.child;
  8.                 while (q.next != null) {
  9.                     q = q.next;
  10.                 }
  11.                 p.next = p.child;
  12.                 p.child.prev = p;
  13.                 p.child = null;
  14.                 q.next = next;
  15.                 if (next != null) {
  16.                     next.prev = q;
  17.                 }
  18.             }
  19.             p = p.next;
  20.         }
  21.         return head;
  22.     }
  23. }