430. 扁平化多级双向链表

🟠   🔖  深度优先搜索 链表 双向链表  🔗 力扣 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 是链表的节点总数。这个算法递归地处理了多级链表中的每个节点，每个节点都只处理一次。
• 空间复杂度：O(1)。

代码

/**
 * @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	二叉树展开为链表	[✓]	栈 树 深度优先搜索 2+
1660	纠正二叉树 🔒		树 深度优先搜索 广度优先搜索 2+