简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
今天给大家分享的书籍《Python程序员面试算法宝典》第一章第四小节：链表进行重新排序。
如果你是第一次看，也许，你可以看看本系列下面的文章：
Smaller And Smarter Python数据结构：链表逆转
Smaller And Smarter Python数据结构：删除无序链表重复结点
Smaller And Smarter Python数据结构：链表相加
今日问题
""" 目标：写一段程序，对链表进行重新排序 例如： 输入-> L1->L2->L3->...->Ln-1->Ln 输出-> L1->Ln->L2->Ln-1... """ """ Objective: write a program to reorder the linked list For example: Input - > L1 - > L2 - > L3 -> ... - > ln-1 - > LN Output - > L1 - > ln - > L2 - > ln-1... """
题目要求
（1）在原来链表的基础上进行排序，即不能申请新的结点；
（2）只能修改结点的next域，不能修改数据域。
首先我们写好链表的基本操作，在a_0_base.py文件中，目前包含对链表的定义类，初始化函数，遍历函数。（带头结点）
# -*- coding: utf-8 -*- """ @author = 老表 @date = 2019-10-19 @个人微信公众号 : 简说Python """ # 链表数据结构定义 class ListNode: def __init__(self, x): self.data = x 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 ergodic_list(head): cur = head.next while cur: print(cur.data) cur = cur.next
解题
开始程序前需提前导入前面写好的链表基本操作包，在Linked_list的a_0_base.py中。
from Linked_list.a_0_base import ListOperation
思路分析
""" 核心思想：先将链表前 后段分开，然后将后半段链表逆转， 再遍历链表，将处理好的后半段链表结点插入到前半段链表中。 优点：该题比较综合，遍历链表，逆转链表，插入结点 时间复杂度：O(N) 空间复杂度：O(1) """
注意：代码中的注释部分可以不需要，是我自己编写、调试bug时用的，之所以留在上面，主要为了方便大家调试代码和理解代码。
辅助函数：查找链表中间结点
# 辅助函数：找出链表中间结点 def find_mid_link(head): fast_node = head.next # 快指针,每次后移两位 slow_node = head.next # 慢指针,每次后移一位 while fast_node and fast_node.next: # 遍历链表，快指针遍历结束时，慢指针应该刚好遍历到一半 pre_slow_node = slow_node # 记录慢指针前驱结点，方便断开前后半部分链表 slow_node = slow_node.next # 慢指针后移，步进1 fast_node = fast_node.next.next # 快指针后移，步进2 pre_slow_node.next = None # 断开前半部分链表与后半部分链表连接 return slow_node # 返回中间结点
辅助函数：不带头结点链表逆转
# 辅助函数：不带头结点链表逆转 def reverse_list(l1): if not l1 or not l1.next: # 空链表或只有一个结点 return l1 cur_node = l1.next # 记录当前结点 pre_node = l1 # 记录前驱结点 l1.next = None # 设置尾结点 # print("------------------") while cur_node: # print(cur_node.data) next_node = cur_node.next # 记录后继结点 cur_node.next = pre_node # 当前结点反向指向前驱结点 pre_node = cur_node # 前驱结点后移 cur_node = next_node # 当前结点后移 # print(pre_node.data) return pre_node # 返回链表表头结点
主功能函数
def reorder_link_one(head): """ :type head: ListNode :rtype: ListNode """ if not head.next: # 空链表 return head # 返回头结点 mid_node = find_mid_link(head) # 查找链表中间结点 # print("------------------") # s0 = ListOperation() # s0.ergodic_list(mid_node) # print("------------------") # s0.ergodic_list(head) mid_node = reverse_list(mid_node) # 逆转后半部分链表,无头结点 # print("------------------") # ListOperation.ergodic_list(mid_node) cur_node = head.next # 记录前半段链表第一个结点 while cur_node.next: # 遍历前半段结点，将后半段结点插入 temp_node = cur_node.next # 记录后继结点 cur_node.next = mid_node # 插入 cur_node = temp_node # 后移 temp_node = mid_node.next # 记录后继结点 mid_node.next = cur_node # 插入 mid_node = temp_node # 后移 cur_node.next = mid_node # 将mid_node最后一个结点插入 return head # 返回当前子链表头结点
测试代码
# 当然，也许还有别的方法，比如建一个辅助的链表 # 欢迎你说出你的想法 # 程序入口，测试函数功能 if __name__ == "__main__": s0 = ListOperation() # 初始化一个链表基本操作对象实例 list_data = [1, 2, 3, 4, 5, 6] # 链表初始化数据 head = s0.init_list(list_data) # 初始化链表，带头结点 s0.ergodic_list(head) # 未操作前，遍历打印链表 head = reorder_link_one(head) # 测试方法一 print("---------------------") s0.ergodic_list(head) # 操作后，遍历打印链表
本文代码思路部分来自书籍《Python程序员面试宝典》，书中部分代码有问题或未提供代码，文中已经修改过了，并添加上了丰厚的注释，方便大家学习，后面我会把所有内容开源放到Github上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。
希望大家多多支持。
大家好，我是老表
觉得本文不错的话，转发、留言、点赞，是对我最大的支持。
