简说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数据结构：单链表删除给定结点，只给该结点+判断&找出交叉结点Smaller And Smarter Python数据结构：展开链接链表（超级有趣的链表）
解题准备
首先我们写好链表的基本操作，在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, end=" ") 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
一、链表逆转引申题
Smaller And Smarter Python数据结构：链表逆转
""" 第一小节引申： 1、对不带头结点的单链表进行逆序 2、从尾到头输出链表结点值 """
1、对不带头结点的单链表进行逆序
# 1、对不带头结点的单链表进行逆序 def link_reverse(link_node): if not link_node or not link_node.next: return link_node # 链表只有一个结点，或者为空链表，或者递归找到尾结点 cur_node = link_node.next head_node = link_reverse(cur_node) # 递归，往后遍历,找到尾结点 cur_node.next = link_node # 逆转：后面的数指向前面的数 link_node.next = None # 断开之前的链接 return head_node # 返回原链表尾结点
2、对不带头结点单链表从尾到头输出链表结点值
# 2、对不带头结点单链表从尾到头输出链表结点值 def link_reverse_print(link_node): if not link_node: return link_node # 链表只有一个结点，或者为空链表，或者递归找到尾结点 cur_node = link_node head_node = link_reverse_print(cur_node.next) # 递归，往后遍历,到尾结点然后开始向前回溯 print(cur_node.data, end=" ") # 打印结点值 return head_node # 返回前一个结点
二、删除无序链表重复结点引申题
Smaller And Smarter Python数据结构：删除无序链表重复结点
""" 第二小节引申： 如何从有序链表中移除重复项(带头结点链表) """
如何从有序链表中移除重复项
# 如何从有序链表中移除重复项 def remove_duplicates(head): if not head.next or not head.next.next: # 空链表或者只有一个结点 return head cur_node = head.next # 链表第一个结点 while cur_node.next: # 遍历去重 next_node = cur_node.next # 获取下个相邻结点 # print(next_node.data) if cur_node.data == next_node.data: # 比较相邻结点值相不相等 cur_node.next = next_node.next # 相等，去除，让当前结点指向next的下一个结点 else: cur_node = cur_node.next # 相邻结点不相等，后移，继续遍历 return head # 返回头结点
三、链表进行重新排序引申
Smaller And Smarter Python数据结构：链表进行重新排序
""" 第四小节引申： 如何查找链表中间结点(带头结点链表) """
如何查找链表中间结点
# 如何查找链表中间结点 def get_middle_node(head): if not head.next or not head.next.next: # 空链表或者只有一个结点 return head slow_node = head.next # 慢指针，开始点 fast_node = head.next # 快指针，开始点 while fast_node.next and fast_node.next.next: # 遍历链表 fast_node = fast_node.next.next # 快指针，每次后移两位 slow_node = slow_node.next # 慢指针，每次后移一位 if ListOperation.get_len_list(head) % 2 == 0: return slow_node, slow_node.next # 如果链表结点个数为偶数，则有两个中间结点 else: # 链表结点数是奇数个则只有一个中间结点 return slow_node # 返回middle_node
四、链表倒数第K个元素引申
Smaller And Smarter Python数据结构：链表倒数第K个元素+检测单链表环算法
""" 第五小节引申： 如何将单链表向右旋转k个位置 要求解读：把链表倒数的k个元素移到链表开头，就表示旋转了k个位置 输入：-> 1 -> 2 -> 3 -> 4 -> 5 输入：k = 2 输出：-> 4 -> 5 -> 1 -> 2 -> 3 """
如何将单链表向右旋转k个位置
# 辅助函数：快慢指针找倒数第k个元素 def find_last_k(head, k): fast_node = head.next # 设置快指针 slow_node = head.next # 设置慢指针 temp = k # 临时遍量 while fast_node: # 遍历 fast_node = fast_node.next # 快指针后移 temp = temp - 1 # temp减一，记录遍历次数 if temp < 0: # 遍历次数过k次后，慢指针也开始遍历,相当于快指针先后移k次 slow_node = slow_node.next # 慢指针后移 return slow_node # 返回倒数第k个结点 def right_rotation_k(head, k): if not head.next or not head.next.next: # 空链表或者只有一个结点 return head # 第一步：找到倒数第k+1和倒数第k个元素，断开链表 pre_node = find_last_k(head, k+1) # 倒数第k+1 next_node = pre_node.next # 倒数第k # 第二步：以倒数第k个结点为界限，断开链表 pre_node.next = None # 第三步：让头结点指向倒数第k个结点，让尾结点指向第一个结点（原链表） # 将原链表倒数的k个元素插到最开头的地方 first_node = head.next # 记录原链表第一个结点 head.next = next_node # 让头结点指向倒数第k个结点 while next_node.next: # 找到尾结点 next_node = next_node.next next_node.next = first_node # 让尾结点指向原链表第一个结点 # 完成插入（完成旋转） return head
五、检测单链表环引申
Smaller And Smarter Python数据结构：链表倒数第K个元素+检测单链表环算法
""" 第六小节引申： 如果链表存在环，如何找到环入口 """
找出有环链表的环入口结点
# 辅助函数：判断链表是否有环 def check_ring(head): if not head.next: # 空链表肯定不存在环 return None # 直接返回None fast_node = head.next # 快指针，初始值为第一个结点 slow_node = head.next # 慢指针，初始值为第一个结点 while slow_node: # 遍历查找 slow_node = slow_node.next # 慢指针，每次位移一 fast_node = fast_node.next.next # 快指针，每次位移二 if slow_node == fast_node: # 判断快慢指针是否相同 return slow_node # 相同，则有环，返回相遇结点 return None # 否则无环，返回None # 找出有环链表的环入口结点 def get_ring_node(head): meet_node = check_ring(head) # 判断是否有环，并找到快慢指针相遇结点 first_node = head.next # 链表第一个结点 while first_node != meet_node: # 遍历链表，查找环入口 # 当遍历到当前结点和快慢指针相遇结点相同时，则是环入口位置 first_node = first_node.next meet_node = meet_node.next ''' 为什么这样做可以找到环入口？ 1.在我们判断链表是否有环时，有环情况会返回快慢指针相遇结点， 注意快指针比慢指针快一倍，快指针遍历圈数对于1，才有可能快慢 指针相遇，相遇时在环内 2.相遇结点到环入口的距离和第一个结点到环入口的距离（顺序遍历） 是相等的 3.如果不明白，建议在纸上把整个过程画出来 ''' return first_node # 返回环入口，即两链表相交结点
六、单链表删除给定结点引申
Smaller And Smarter Python数据结构：单链表删除给定结点，只给该结点+判断&找出交叉结点
""" 第十小节引申： 只给定单链表中的某个结点p(非空结点)，如何在p前面插入一个结点 要求解读：和本节的只给定一个结点然后删除该结点遇到的问题是一样的， 要删除或者插入一个结点，必须得知道该结点的前驱结点，但现在只有一 个结点，所以我们只能采用后插然后交换结点数据域。 原链表：-> 1 -> 2 -> 3 -> 4 -> 5 输入：2（表示链表第二个结点） 输入：10（表示待插入结点） 输出：-> 1 -> 10 -> 2 -> 3 -> 4 -> 5 """
只给定单链表中的某个结点p(非空结点)，如何在p前面插入一个结点
def insert_in_p(p, q): """ :param p: 原链表的一个结点 :param q: 待插入结点 :return: Bool 表示插入成功与否 """ p_next = p.next # 找到p的下一个结点 p.next = q q.next = p_next # 将q插入到p与p_next之间 temp = p.data p.data = q.data q.data = temp # p、q结点的数据域互换 return True
七、找出交叉结点引申
Smaller And Smarter Python数据结构：单链表删除给定结点，只给该结点+判断&找出交叉结点
""" 第十一小节引申： 如何单链表有环，如何判断两个链表是否相交 要求解读：首先我们要理解的是，单链表有环的话，环一定末尾， 因为单链表只有一个指向next,所以一个有环的单链表和一个没 环的单链表肯定不相交；两个有环的单链表才有可能相交，而且 两个链表环肯定是一样的（不可能在环后相交，有环的单链表实 际可以把环看作一个尾结点），实际上我们只需找出一个链表的 环上的一个结点，然后判断该结点在不在另一个链表即可。 注意：如果是找一个非环入口的结点，则当两链表不相交，判断该 环结点在不在另一个链表（带环）内时，会陷入死循环；所以最好 的办法是找出两个链表的环结点，如果相同，则说明相交，否则， 不相交。（也可以找出一个环结点，然后遍历另一个链表，看看该 环结点是否在另一个链表） 输入：-> 1 -> 2 -> 3 -> 4 -> 5 输入：k = 2 输出：-> 4 -> 5 -> 1 -> 2 -> 3 """
如何单链表有环，如何判断两个链表是否相交
# 辅助函数：判断链表是否有环 def check_ring(head): if not head.next: # 空链表肯定不存在环 return None # 直接返回None fast_node = head.next # 快指针，初始值为第一个结点 slow_node = head.next # 慢指针，初始值为第一个结点 while slow_node: # 遍历查找 slow_node = slow_node.next # 慢指针，每次位移一 fast_node = fast_node.next.next # 快指针，每次位移二 if slow_node == fast_node: # 判断快慢指针是否相同 return slow_node # 相同，则有环，返回相遇结点 return None # 否则无环，返回None # 辅助函数：找出有环链表的环入口结点 def get_ring_node(head): meet_node = check_ring(head) # 判断是否有环，并找到快慢指针相遇结点 first_node = head.next # 链表第一个结点 while first_node != meet_node: # 遍历链表，查找环入口 # 当遍历到当前结点和快慢指针相遇结点相同时，则是环入口位置 first_node = first_node.next meet_node = meet_node.next ''' 为什么这样做可以找到环入口？ 1.在我们判断链表是否有环时，有环情况会返回快慢指针相遇结点， 注意快指针比慢指针快一倍，快指针遍历圈数对于1，才有可能快慢 指针相遇，相遇时在环内 2.相遇结点到环入口的距离和第一个结点到环入口的距离（顺序遍历） 是相等的 3.如果不明白，建议在纸上把整个过程画出来 ''' return first_node # 返回环入口，即两链表相交结点 def whether_cross(head1, head2): first_ring = check_ring(head1) second_ring = check_ring(head2) # 检查链表1，2是否都有环 if not (first_ring and second_ring): return False # 找出环结点 ring1_node = get_ring_node(head1) ring2_node = get_ring_node(head2) # 判断环结点是否相同 if ring1_node == ring2_node: return True else: return False
到此链表已经结束了，有时间，我会把数据结构中链表操作和解题技巧归纳总结，发布到知识星球：简说编程。
