简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
今天给大家分享的书籍《Python程序员面试算法宝典》第一章第七小节：翻转链表相邻结点和第一章第八节：翻转链表k个相邻结点。
如果你是第一次看，也许，你可以看看本系列下面的文章：
Smaller And Smarter Python数据结构：链表逆转Smaller And Smarter Python数据结构：删除无序链表重复结点Smaller And Smarter Python数据结构：链表相加Smaller And Smarter Python数据结构：链表进行重新排序Smaller And Smarter Python数据结构：链表倒数第K个元素+检测单链表环算法
今日问题 ：翻转链表相邻结点
""" 目标：写一段程序，翻转链表相邻结点 例如： 输入-> 1->2->3->4->5 输出-> 2->1->4->3->5 Goal: write a program to flip the adjacent nodes of the linked list For example: Input - > 1 - > 2 - > 3 - > 4 - > 5 Output - > 2 - > 1 - > 4 - > 3 - > 5 """
解题准备
首先我们写好链表的基本操作，在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 # 获取链表长度 @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
解题
开始程序前需提前导入前面写好的链表基本操作包和结点数据结构，在Linked_list的a_0_base.py中。
from Linked_list.a_0_base import ListOperation
方法一：遍历交换法
解题思路
""" Method One : 遍历交换法 核心思想：遍历链表，记录从往后，记录相邻的两个结点， 改变结点指向，实现交换（实际需要四个结点，比如： a->b->c->d b，c 交换，要修改三处链表指向 故a,b,c,d四个结点都要记录）。 时间复杂度：O(N) 空间复杂度：O(1) """
代码
def flip_adjacent_node_one(head): if not head.next: # 空链表 return head # 返回头结点 pre_node = head # 记录前驱结点 cur_node = head.next # 记录当前结点 while cur_node.next: # 遍历交换（cur_node 与 cur_node.next交换） next_node = cur_node.next.next # 记录下一个cur_node，因为相邻交换没两个进行一次，故下一个为cur_node.next.next pre_node.next = cur_node.next # 1、交换第一步，前驱结点指向cur_node的后一个结点（cur_node.next） cur_node.next.next = cur_node # 2、交换第二步，cur_node.next反指,指向cur_node cur_node.next = next_node # 3、交换第三步，cur_node指向cur_node.next.next，完成交换 """(原本是cur_node.next指向cur_node.next.next， 但现在cur_node与cur_node.next交换位置， 故让cur_node指向cur_node。next.next)""" pre_node = cur_node # 前驱结点后移 cur_node = next_node # 当前结点后移 return head # 返回头结点
方法二：递归交换法
解题思路
""" Method Two ：递归交换法 核心思想：遍历链表，每次将相邻结点的第二个结点的 next指针指向前一个结点，然后将第一个结点的指针指 向下一组已经翻转好的相邻结点的第一个结点。 时间复杂度：O(N) 空间复杂度：O(1) """
代码
def flip_adjacent_node_two(head): if not head: # 空链为空 或者 递归到尾 return head # 开始回溯，返回结点 if head.data == "head": # 去掉头结点，直接从第一个结点开始 head = head.next first_node = head # 链表第一个结点 second_node = head.next # 获取第二个结点 first_node.next = flip_adjacent_node_two(head.next.next) # 递归，传递第三个结点作为参数 # 回溯时，让第一个结点指向下一组已经翻转好的相邻结点的第一个结点 second_node.next = first_node # 回溯时，让第二个结点反指向第一个结点 return second_node # 返回头结点
测试代码
# 当然，也许还有别的方法，比如建一个辅助的链表 # 欢迎你说出你的想法 # 程序入口，测试函数功能 if __name__ == "__main__": list_data = [1, 2, 3, 4, 5, 6] # 链表初始化数据 head = ListOperation.init_list(list_data) # 初始化链表，带头结点 ListOperation.ergodic_list(head) # 未操作前，遍历打印链表 # head = flip_adjacent_node_one(head) # 测试方法一 head.next = flip_adjacent_node_two(head) # 测试方法二 print("---------------------") ListOperation.ergodic_list(head) # 操作后，遍历打印链表
今日问题 ：翻转链表k个相邻结点
""" 目标：写一段程序，k个为一组翻转链表相邻结点 例如： 输入 k = 3 输入-> 1->2->3->4->5->6->7 输出-> 3->2->1->6->5->4->7 Goal: write a program, K for a group of adjacent nodes of flip list For example: Input k = 3 Input - > 1 - > 2 - > 3 - > 4 - > 5 - > 6 - > 7 Output - > 3 - > 2 - > 1 - > 6 - > 5 - > 4 - > 7 """
解题准备
首先我们写好链表的基本操作，在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: a = 1 # 根据链表数据初始化链表 @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_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(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
解题
开始程序前需提前导入前面写好的链表基本操作包和结点数据结构，在Linked_list的a_0_base.py中。
from Linked_list.a_0_base import ListOperation
解题思路
""" Method One : 分组逆转法 核心思想：以k个结点为一组，每组看作一个子链表， 逆转每个子链表，然后让逆转后的最后一个结点指向 下一组，继续逆转，直到结束。 时间复杂度：O(N) 空间复杂度：O(1) """
辅助函数
''' 在做 链表重新排序 时，我们就已经写个这个函数 ''' # 辅助函数：不带头结点链表逆转 def reverse_list(l1): if not l1 or not l1.next: # 空链表或只有一个结点 return l1 cur_node = l1.next # 记录当前结点 pre_node = l1 # 记录前驱结点 l1.next = None # 设置尾结点 while cur_node: next_node = cur_node.next # 记录后继结点 cur_node.next = pre_node # 当前结点反向指向前驱结点 pre_node = cur_node # 前驱结点后移 cur_node = next_node # 后移遍历 return pre_node # 返回逆转后的第一个结点
功能代码
def flip_k_node_one(head, k): if not head.next: # 空链表 return head # 返回头结点 pre_node = head # 记录前驱结点 begin_node = head.next # 记录每组开始结点 while begin_node: # 遍历分组逆转，连接 i = 1 # 分组标记 i < k end_node = begin_node # 记录每组尾结点 while i < k: # 遍历找到每组尾结点 if end_node.next: end_node = end_node.next else: return head # 剩余结点不足k个结点，说明分组转换完成 i = i + 1 # 标记值后移 # print("222222", i) next_node = end_node.next # 记录下一组开始结点 end_node.next = None # 断开前一组与后一组的链接 pre_node.next = reverse_list(begin_node) # 逆转前一组的子链，返回逆转后的表尾结点，让开始结点指向该结点 # print(pre_node.next.data) begin_node.next = next_node # 前一组逆转好的尾结点指向下一组的第一个结点 pre_node = begin_node # 前驱结点后移，即成为前一组的尾结点，相当于后一组的头结点 begin_node = next_node # 开始结点后移，成为后一组的第一个结点 return head # 返回头结点
测试代码
# 当然，也许还有别的方法，比如建一个辅助的链表 # 欢迎你说出你的想法 # 程序入口，测试函数功能 if __name__ == "__main__": list_data = [1, 2, 3, 4, 5, 6, 7] # 链表初始化数据 head = ListOperation.init_list(list_data) # 初始化链表，带头结点 ListOperation.ergodic_list(head) # 未操作前，遍历打印链表 len_list = ListOperation.get_len_list(head) # 获取链表长度 k = int(input("请输入参数K in (0, %d] ： " % len_list)) # 输入参数k值 while k > len_list: # 基本判断，过滤 print("k值过大，k in (0, %d]" % len_list) k = int(input("请重新输入参数K：")) head = flip_k_node_one(head, k) # 测试方法一 print("---------------------") ListOperation.ergodic_list(head) # 操作后，遍历打印链表
本文代码思路部分来自书籍《Python程序员面试宝典》，书中部分代码有问题或未提供代码，文中已经修改过了，并添加上了丰厚的注释，方便大家学习，后面我会把所有内容开源放到Github上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。
希望大家多多支持。
大家好，我是老表
觉得本文不错的话，转发、留言、点赞，是对我最大的支持。
