简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
今天给大家分享的书籍《Python程序员面试算法宝典》第一章第十二小节：链表进行重新排序。
如果你是第一次看，也许，你可以看看本系列下面的文章：
Smaller And Smarter Python数据结构：链表逆转Smaller And Smarter Python数据结构：删除无序链表重复结点Smaller And Smarter Python数据结构：链表相加Smaller And Smarter Python数据结构：链表进行重新排序Smaller And Smarter Python数据结构：链表倒数第K个元素+检测单链表环算法Smaller And Smarter Python数据结构：翻转链表相邻结点+k个相邻结点Smaller And Smarter Python数据结构：合并两个有序链表Smaller And Smarter Python数据结构：单链表删除给定结点，只给该结点+判断&找出交叉结点
今日问题
""" 目标：写一段程序，展开链接链表 例如： 输入-> 3 -> 10 -> 15 -> 24 ｜ ｜ ｜ ｜ 4 11 16 26 ｜ ｜ ｜ ｜ 7 16 19 36 ｜ 33 输出-> 3 -> 4 -> 7 -> 10 -> 11 -> 15 -> 16 -> 16 -> 19 -> 24 -> 26 -> 33 -> 36 Goal: write a program to expand the linked list For example: Input-> 3 -> 10 -> 15 -> 24 ｜ ｜ ｜ ｜ 4 11 16 26 ｜ ｜ ｜ ｜ 7 16 19 36 ｜ 33 Output - > 3 - > 4 - > 7 - > 10 - > 11 - > 15 - > 16 - > 16 - > 19 - > 24 - > 26 - > 33 - > 36 """
有趣的问题：怎么初始化和遍历这样一个链表
# 初始化特殊链表 @staticmethod def init_snode(right_data, down_data): # 初始化一个头指针 head = SNode("head") cur = head for i in range(len(right_data)): right_node = SNode(right_data[i]) # right,主干 right_node.next = ListOperation.init_list(down_data[i]).next # down cur.right = right_node cur = right_node # 相当于 cur = cur.next，后移 return head # 遍历特殊链表 @staticmethod def ergodic_s_list(head): right_node = head.right while right_node: print(right_node.data, end=" ") down_node = right_node.next while down_node: print(down_node.data, end=" ") down_node = down_node.next print() print("*************************") right_node = right_node.right
你能看懂吗？
1、 初始化时，输入两个参数
def init_snode(right_data, down_data) right_data : 主干道结点数据域（right方向），列表类型。 down_data ：down方向链表数据域，列表类型。 初始化right方向链表同时，初始化down方向链表， 每个right结点对应一个down方向链表。
2、 遍历时，输入一个参数
def ergodic_s_list(head) head ：特殊链表的头结点（right方向头结点） 遍历rigth方向链表，每遍历到一个right结点， 就按该结点遍历down方向链表。
解题前准备
首先我们写好链表的基本操作，在a_0_base.py文件中，目前包含对链表的定义类，初始化函数，遍历函数。（带头结点）
# -*- coding: utf-8 -*- """ @author = 老表 @date = 2019-10-19 @个人微信公众号 : 简说Python """ import random # 链表数据结构定义 class ListNode: def __init__(self, x): self.data = x self.next = None # 特殊链表结构定义 class SNode: def __init__(self, x): self.data = x self.right = None self.next = None class ListOperation: # 根据链表数据初始化链表，带头结点 @staticmethod def init_list(n_list): # 初始化一个头指针 head = ListNode("head") cur = head for i in n_list: node = ListNode(i) cur.next = node cur = node # 相当于 cur = cur.next，后移 return head # 根据链表数据初始化链表，不带头结点 @staticmethod def init_list_n(n_list): head = ListNode(n_list[0]) cur = head for i in range(1, len(n_list)): node = ListNode(n_list[i]) cur.next = node cur = node # 相当于 cur = cur.next，后移 return head # 根据链表数据初始化一个有环的链表 @staticmethod def init_ring_list(n_list): # 初始化一个头指针 head = ListNode("head") cur = head for i in n_list: node = ListNode(i) cur.next = node cur = node # 相当于 cur = cur.next，后移 cur.next = head.next.next.next.next # 随意的，让最后一个结点指向第四个结点 return head # 遍历链表,不带头结点 @staticmethod def ergodic_list_n(head): # print(head.data) cur = head while cur: print(cur.data, end=" ") cur = cur.next # 遍历链表 @staticmethod def ergodic_list(head): # print(head.data) cur = head.next while cur: print(cur.data) cur = cur.next # 获取链表长度 @staticmethod def get_len_list(head): cur = head.next len_list = 0 while cur: len_list = len_list + 1 cur = cur.next return len_list # 随机获取一个结点 @staticmethod def get_random_node(head): cur = head.next i = 0 len_list = ListOperation.get_len_list(head) while cur.next: if i == random.randint(0, len_list-1): break cur = cur.next return cur # 制作一个随机交叉链表 @staticmethod def get_random_link(n_list, head1): p = ListOperation.get_random_node(head1) # 获取一个链表1的随机结点 # 初始化一个头指针 head = ListNode("head") cur = head for i in n_list: node = ListNode(i) cur.next = node cur = node # 相当于 cur = cur.next，后移 cur.next = p # 将链表1的从p结点开始的后半部分，添加到当前链表后 # 当前链表与链表1相交 return head # 返回新创建的链表头结点 # 初始化特殊链表 @staticmethod def init_snode(right_data, down_data): # 初始化一个头指针 head = SNode("head") cur = head for i in range(len(right_data)): right_node = SNode(right_data[i]) # right,主干 right_node.next = ListOperation.init_list(down_data[i]).next # down cur.right = right_node cur = right_node # 相当于 cur = cur.next，后移 return head # 遍历特殊链表 @staticmethod def ergodic_s_list(head): right_node = head.right while right_node: print(right_node.data, end=" ") down_node = right_node.next while down_node: print(down_node.data, end=" ") down_node = down_node.next print() print("*************************") right_node = right_node.right
解题
开始程序前需提前导入前面写好的链表基本操作包和结点数据结构，在Linked_list的a_0_base.py中。
from Linked_list.a_0_base import ListOperation
思路分析
""" Method One : 归并排序（递归）法 核心思想：先遍历主干结点（right方向），递归过去，到尾结点， 然后回溯，主干结点相当于down方向的头结点，依次从后将相邻的 两个链表合并成一个有序链表，然后返回，继续合并，直至回溯结 束。 时间复杂度：O(N) 空间复杂度：O(1) """
辅助函数：合并两个有序链表
# 辅助函数：合并两个有序链表 def merge_list(l1, l2): # 如果有一个链表为空， # 则直接返回另一个链表 if not l1: return l2 if not l2: return l1 # 判断两个链表结点数据值大小 if l1.data < l2.data: # 链表2的结点数据值大 result = l1 # 链表1在前 l1.next = merge_list(l1.next, l2) # 递归遍历，把小结点插到后面 else: # 链表2的结点数据值大 result = l2 # 链表2在前 l2.next = merge_list(l1, l2.next) # 递归遍历，把小结点插到后面 return result # 返回小结点
主功能函数
def expand_link_list_one(head): # 空链表直接返回头结点 if not head or not head.right: return head root = head # 记录当前头结点（right线） # 递归处理主干链表 root.right = expand_link_list_one(root.right) # 把root结点对应的链表与右边的链表合并 root = merge_list(root, root.right) # 合并两个有序链表 return root
测试代码
# 当然，也许还有别的方法，比如建一个辅助的链表 # 欢迎你说出你的想法 # 程序入口，测试函数功能 if __name__ == "__main__": # 第一步：初始化特殊链表 # 1.初始化特殊链表主干（right走向） right_data = [3, 10, 15, 24] # 主干道数据，right list_data1 = [4, 7, 33] # 链表1初始化数据，down list_data2 = [11, 16] # 链表2初始化数据，down list_data3 = [16, 19] # 链表3初始化数据，down list_data4 = [26, 36] # 链表4初始化数据，down down_data = [list_data1, list_data2, list_data3, list_data4] # down data head = ListOperation.init_snode(right_data, down_data) # 初始化特殊链表，带头结点 ListOperation.ergodic_s_list(head) # 未操作前，遍历打印特殊链表 print("___________________________") result = expand_link_list_one(head.right) # 测试方法一 head.next = result ListOperation.ergodic_list(head) # 操作后，打印链表
本文代码思路部分来自书籍《Python程序员面试宝典》，书中部分代码有问题或未提供代码，文中已经修改过了，并添加上了丰厚的注释，方便大家学习，后面我会把所有内容开源放到Github上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。
希望大家多多支持。
大家好，我是老表
觉得本文不错的话，转发、留言、点赞，是对我最大的支持。
欢迎关注微信公众号：简说Python
关注后回复：1024，可以领取精选编程学习电子书籍。
