Python 中的链表展平

如果我们给定一个链表，其中每个节点本身就是一个单独的链表，并且有两个相同类型的指针。

1. 一个指针指向主链表的下一个节点（在下面的程序中称为“prim”指针）。
2. 一个指针指向次链表的下一个节点（在下面的程序中称为“sec”指针）。

主链表和次链表都应该是排序的，并且最终形成的扁平化链表也应该是排序的。

示例

输入

输出

6 -> 7 -> 9 -> 15 -> 21 -> 25 -> 26 -> 29 -> 30 -> 30 -> 31 -> 51 -> 56

输入

输出

4 -> 5 -> 8 -> 9 -> 10 -> 15 -> 15 -> 17 -> 21 -> 30 

策略是定义一个函数来合并链表。我们将使用 merge() 函数顺序合并链表，并通过递归地将当前链表合并到最近的扁平化链表中。我们将使用 sec 指针连接扁平化链表的节点。

该问题的算法如下：

• 我们将递归地将当前迭代的链表与下一个链表进行合并。
• 如果当前迭代的链表没有节点，即它是空的，或者下一个链表是 None，则返回当前迭代的链表。此条件将作为基本条件。
• 我们将从合并最近的链表开始。
• 在合并当前链表和先前扁平化链表后，我们将返回当前迭代链表的头节点。

上述技术实现如下：

代码

输出

The flattened linked list is: 
6 7 9 15 21 25 26 29 30 30 31 51 56 

时间复杂度：该程序的时间复杂度为 O(n * n * m)。其中 N 是主链表中的总节点数，M 是单个子链表中的节点数。

辅助空间：O(n * m)。

因为我们同时合并两个链表，

• 当我们合并前两个子链表时，时间复杂度将为 O(m + m) = O(2m)。
• 在下一步，我们将一个子链表合并到新的已合并链表中。因此，时间复杂度将为 O(2m + m) = O(3M)。
• 在下一步，我们将合并另一个链表。因此，时间复杂度将为 O(3m + m)。
• 这样，我们将继续将子链表合并到已合并链表中。
• 此步骤将重复 n 次；因此，此方法总共将花费 O(2m + 3m + 4m + …. n * m) = (2 + 3 + 4 + … + n)*m 的时间。
• 进一步求解上述方程：时间复杂度 = O((n * n + n - 2) * m / 2)
• 当 n 很大时，上述方程的近似值为 O(n * n * m)。

由于我们使用的是递归方法，此方法的空间复杂度为 O(n * m)。使用的递归函数将创建一个递归栈。该栈的大小将等同于给定嵌套链表中存在的总节点数，即 n * m。

使用优先队列扁平化链表

该方法是创建一个最小堆，并将每个链表的头节点放入该数据结构中。然后，使用 Extract-min 方法，从优先队列中获取最小整数，并使用该最小元素在链表中继续操作。

为了实现这一策略，我们将使用以下算法：

• 将每个链表的头节点推入最小堆优先队列。
• 然后，当优先队列不为空时，我们将从中提取最小整数值节点，并且如果下一个节点指向最小值为止的节点，则我们将该节点推入优先队列。
• 此外，在提取最小值的节点后，我们将每次打印该节点的值。

我们将使用 Python 实现此算法，如下所示。

代码

输出

30 9 7 6 51 26 21 56 31 30 29 

时间复杂度：该方法的时间复杂度为 O(N * M * log(N))。其中 N 是主链表或初始链表中的节点数，M 是单个子链表中的节点数。

辅助空间：此方法的空间复杂度为 O(N)。其中 N 是主链表中存在的节点数。