编写 Python 代码展平链表

在本教程中，我们将编写 Python 代码来扁平化给定的链表。给定的链表由每个节点表示一个链表，并包含两个指向其类型的指针。

第一个指针指向下一个节点，第二个指针（bottom 指针）指向该节点作为头部的链表。每个子链表都按排序顺序排列。

这里的扁平化意味着所有节点都必须出现在同一级别，同时保持排序顺序。

让我们看问题陈述。

问题陈述

示例 -

输入

输出

5-> 7-> 8- > 10 -> 19-> 20-> 22-> 28-> 30-> 35-> 40-> 45-> 50.

示例 - 2

输入

输出

5->7->8->10->19->22->28->30->50

解决方案

在此方法中，我们首先将其转换为常规列表，然后扁平化元素。让我们理解以下示例。

示例 -

输出

Flattened linked list: [5, 7, 8, 30, 10, 19, 28, 22, 50]

解释 -

在上面的代码中，我们首先创建了带有 next 和 next to next 指针的节点。我们创建了 flatten_linked_list()，它接受链表的 head 作为输入。它通过遍历链表并将每个节点的 data 添加到列表中来将链表转换为常规列表。然后，它通过递归调用 flatten_linked_list 函数来扁平化列表，以处理遇到的任何子节点。最后，它返回扁平化后的列表。

该程序创建了示例链表，如前所述，然后调用链表 head 上的 flatten_linked_list() 函数。生成的扁平化列表将作为输出打印。

示例 -

输出

Flattened linked list: [5, 7, 8, 30, 10, 19, 28, 22, 50]

解释 -

在上面的代码中，我们创建了一个 Node 类，它表示链表中的一个节点。每个节点都有一个 data 属性来存储值和两个指针：right 和 down。right 指针用于水平连接节点，down 指针用于垂直连接节点。

该代码还定义了一个 LinkedList 类，该类具有在列表开头插入节点、打印列表以及扁平化列表的方法。

在 LinkedList 类中，insert_at_beginning() 方法接受 head 节点（head_ref）的引用和 data 作为输入。它使用给定的 data 创建一个新节点，并将其 down 指针设置为当前 head。然后，它将 head_ref 更新为指向新节点，从而有效地将新节点插入到列表的开头。返回更新后的 head_ref。

print_list() 方法遍历链表，并打印每个节点的 data，沿着 down 指针移动，直到到达列表末尾。

merge_lists() 方法是一个递归函数，它接受两个列表（a 和 b）作为输入，并将它们合并成一个单一的排序列表。

它比较每个列表 head 处节点的 data，并递归地合并剩余的列表。

合并是通过将当前节点的 down 指针更新为带有剩余节点的递归调用的结果来完成的。当前节点的 right 指针被设置为 None，以确保扁平化的结构。

flatten() 方法是扁平化给定多级链表的主要函数。它以 root 节点作为输入，并通过执行以下步骤递归地扁平化列表：

如果 root 为 None 或右侧没有节点（root.right 为 None），则返回 root。

它递归调用 flatten 来扁平化右侧的子列表。

然后，它使用 merge_lists 方法将当前 root 与扁平化后的右侧子列表合并。

最后，它返回扁平化后的 root。然后，创建 LinkedList 类的实例。

使用 insert_at_beginning() 方法在列表开头插入节点，创建多级结构。

通过调用链表 head 上的 flatten 方法来扁平化列表。

最后，使用 print_list 方法打印扁平化后的列表。