12展开链接列表★★★
题目描述（难度：较难）
给定一个有序链表，其中每个结点也表示一个有序链表，结点包含两个类型的指针：
（1）指向主链表中下一个结点的指针（“right”指针）
（2）指向此结点头的链表（“down”指针）
所有链表都被排序。如下图所示：
实现一个函数 flatten()，该函数用来将链表扁平化成单个链表，扁平化的链表也应该被排序。例如，对于上述输入链表，输出链表应为3->6->8->11->15->21->22->30->31->39->40->45->50。（来源：腾讯）
链表结点结构
class Node:
def __init__(self,data=None):
self.data=data # 数据域
self.right=None # right指针
self.down=None # down指针
方法一
class Node:
def __init__(self,data=None):
self.data=data
self.right=None
self.down=None
class MergeList:
def __init__(self):
self.head=None
# 用来合并两个有序的链表
def merge(self,a,b):
# 如果有其中一个链表为空，直接返回另外一个链表
if a == None:
return b
if b == None:
return a
# 把两个链表头中较小的结点赋值给result
if a.data < b.data:
result = a
result.down = self.merge(a.down, b)
else:
result = b
result.down = self.merge(a, b.down)
return result
# 把链表扁平化处理
def flatten(self,root):
if root == None or root.right == None:
return root
# 递归处理root.right链表
root.right = self.flatten(root.right)
# 把root结点对应的链表与右边的链表合并
root = self.merge(root, root.right)
return root
# 把data插入到链表头
def insert(self,head_ref,data):
new_node =Node(data)
new_node.down = head_ref
head_ref = new_node
# 返回新的表头结点
return head_ref
def printList(self):
temp = self.head
while temp != None:
print (temp.data,'',end='')
temp = temp.down
print ('\n')
复杂度分析
- 时间复杂度为 O ( n ) O(n) O(n)，只对链表进行一次遍历。
- 空间复杂度为 O ( 1 ) O(1) O(1)，只需常量个指针变量来保存结点的地址信息。
主函数
if __name__=="__main__":
L = MergeList()
# 头插法构造链表
L.head = L.insert(L.head, 31)
L.head = L.insert(L.head, 8)
L.head = L.insert(L.head, 6)
L.head = L.insert(L.head, 3)
L.head.right = L.insert(L.head.right, 21)
L.head.right = L.insert(L.head.right, 11)
L.head.right.right = L.insert(L.head.right.right, 50)
L.head.right.right = L.insert(L.head.right.right, 22)
L.head.right.right = L.insert(L.head.right.right, 15)
L.head.right.right.right = L.insert(L.head.right.right.right, 55)
L.head.right.right.right = L.insert(L.head.right.right.right, 40)
L.head.right.right.right = L.insert(L.head.right.right.right, 39)
L.head.right.right.right = L.insert(L.head.right.right.right, 30)
# 扁平化链表
L.head = L.flatten(L.head)
L.printList()
参考文献
[1] 何海涛. 剑指Offer：名企面试官精讲典型编程题（第2版）. 北京： 电子工业出版社，2017
[2] 张波，楚秦. Python程序员面试算法宝典. 北京：机械工业出版社，2018