430. Flatten a Multilevel Doubly Linked List

🟠   🔖  深度优先搜索 链表 双向链表  🔗 LeetCode

题目

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. 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 multilevel data structure as shown in the example below.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear aftercurr and before curr.next in the flattened list.

Return thehead _of the flattened list. The nodes in the list must have all of their child pointers set to _null.

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 shown.

After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3]

Output: [1,3,2]

Explanation: The multilevel linked list in the input is shown.

After flattening the multilevel linked list it becomes:

Example 3:

Input: head = []

Output: []

Explanation: There could be empty list in the input.

Constraints:

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

How the multilevel linked list is represented in test cases:

We use the multilevel linked list from Example 1 above:

1---2---3---4---5---6--NULL

    |

    7---8---9---10--NULL

        |

        11--12--NULL

The serialization of each level is as follows:

[1,2,3,4,5,6,null]

[7,8,9,10,null]

[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, 2, 3, 4, 5, 6, null]

[null, null, 7, 8, 9, 10, null]

[null, 11, 12, null]

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

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

题目大意

你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。

给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。

返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。

解题思路

1. 使用递归遍历多级链表，如果某个节点有子链表，则对子链表进行递归处理。
2. 在递归处理过程中，将当前节点的 next 指针指向递归处理后的子链表，同时将子链表的 prev 指针指向当前节点。
3. 最后，将当前节点的 child 指针置为 null。

这个算法递归地处理了多级链表中的每个节点，每个节点都只处理一次。因此，算法的时间复杂度是 O(n)，其中 n 是链表的节点总数。

代码

/**
 * // Definition for a Node.
 * function Node(val,prev,next,child) {
 *    this.val = val;
 *    this.prev = prev;
 *    this.next = next;
 *    this.child = child;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var flatten = function (head) {
  if (!head) return null;
  const next = head.next;
  const child = head.child;

  // 处理当前节点的子链表
  const flattenChild = flatten(child);
  // 连接当前节点和递归处理后的子链表
  if (flattenChild) {
    head.next = flattenChild;
    flattenChild.prev = head;
    head.child = null;
  }
  // 递归处理后续节点
  const flattenNext = flatten(next);
  // 连接递归处理后的子链表和后续节点
  if (flattenNext) {
    const last = findLast(flattenChild) || head;
    last.next = flattenNext;
    flattenNext.prev = last;
  }
  return head;
};

// 辅助函数：找到链表的最后一个节点
var findLast = function (head) {
  while (head && head.next) {
    head = head.next;
  }
  return head;
};

相关题目

相关题目

• 114. 二叉树展开为链表
• 🔒 Correct a Binary Tree

- [114. 二叉树展开为链表](./0114.md)
- [🔒 Correct a Binary Tree](https://leetcode.com/problems/correct-a-binary-tree)