简说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数据结构：链表进行重新排序
今日问题 ：单链表中的倒数第k个元素
""" 目标：写一段程序，找出单链表中的倒数第k个元素 例如： 输入 k = 3 输入-> 1->2->6->4->5 输出 6 Goal: write a program to find the last K element in the single linked list For example: Input k = 3 Input - > 1 - > 2 - > 6 - > 4 - > 5 Output 6 """
解题准备
首先我们写好链表的基本操作，在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 : 顺序遍历查找 核心思想：假设单链表长度为：len，我们要找单链表的倒数第k个结点， 可以转化为我们要找当链表的第len-k个结点，这样，题目就变成了遍历 单链表的简单问题。 时间复杂度：O(N) 空间复杂度：O(1) """
代码
def find_last_k_one(head, k): cur_node = head.next # 获取链表第一个结点 order = len_list - k # 获取链表倒数第k个结点就相当于获取链表第len_list - k 个结点 while cur_node and order > 0: # 遍历链表，找出第len_list - k 个结点 cur_node = cur_node.next # 后移遍历 order = order - 1 # 记录遍历结点数 return cur_node, k # 返回k和倒数第k个结点
方法二：快慢指针法
解题思路
""" Method Two ：快慢指针法 核心思想：建一个快指针，一个慢指针，快指针比慢指针先移动k步， 然后快、慢指针一起往后移动，最终当快指针遍历完成时，慢指针指 的位置就刚好。 时间复杂度：O(N) 空间复杂度：O(1) """
代码
def find_last_k_two(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个结点
方法三：递归查找
解题思路
""" Method Three ：递归查找 核心思想：很烧脑袋的一种方法，先用递归遍历到表尾， 然后在回溯时候记录回溯次数，当回溯到第k次时，获取 当前结点，并返回，继续回溯直至结束。 问题：怎么去改变回溯后的k值并记录 解决：把k值作为返回值之一 当然也可以用其他方法，如：用if语句隔开递归和k值判断 时间复杂度：O(N) 空间复杂度：O(1) """
代码
""" Method Three ：递归查找 核心思想：很烧脑袋的一种方法，先用递归遍历到表尾， 然后在回溯时候记录回溯次数，当回溯到第k次时，获取 当前结点，并返回，继续回溯直至结束。 问题：怎么去改变回溯后的k值并记录 解决：把k值作为返回值之一 当然也可以用其他方法，如：用if语句隔开递归和k值判断 时间复杂度：O(N) 空间复杂度：O(1) """
测试代码
# 当然，也许还有别的方法，比如建一个辅助的链表 # 欢迎你说出你的想法 # 程序入口，测试函数功能 if __name__ == "__main__": list_data = [1, 2, 3, 4, 5, 6] # 链表初始化数据 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：")) # result = find_last_k_one(head, k) # 测试方法一，逆转链表 # result = find_last_k_two(head, k) # 测试方法二，逆转链表 result = find_last_k_three(head, k) # 测试方法三，逆转链表 print("---------------------") print("链表倒数第{0}个元素为：{1}".format(k, result[0].data))
今日问题 ：检测单链表是否有环
""" 目标：写一段程序，检测一个较大的单链表是否有环 例如： 输入-> 1->2->6->4->5->2 (表示结点地址) 输出 环结点：2 Goal: write a program to check whether a large single chain table has rings For example: Input - > 1 - > 2 - > 6 - > 4 - > 5 - > 2 (表示结点地址) Output ring node: 2 """
解题准备
首先我们写好链表的基本操作，在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 : 借助辅助空间 核心思想：遍历链表，同时将每个结点存入到哈希表中， 并判断当前结点在不在哈希表中，如果在，则证明有环， 否则继续遍历。 时间复杂度：O(N) 空间复杂度：O(N) """
代码
def check_ring_one(head): if not head.next: # 空链表肯定不存在环 return None # 直接返回False cur_node = head.next # 记录第一个结点，后面做前驱结点 dict_all = {cur_node: "node"} # 直接把第一个结点加入字典 while cur_node.next: # 遍历链表 cur_node = cur_node.next # 后移遍历 if cur_node in dict_all: # 判断当前结点是否在字典中 return cur_node # 如果在，说明有环 dict_all[cur_node] = "node" # 不再，将该结点加入字典 return None # 遍历完成，没有触发有环判断，则说明没环，返回None
方法二：快慢指针法
解题思路
"
"" Method Two ：快慢指针法 核心思想：建一个快指针，一个慢指针，快指针每次移动两步，慢指针每次 移动一步，当快指针和慢指针相同时，则说明有环，否则无环。 时间复杂度：O(N) 空间复杂度：O(1) """
代码
def check_ring_two(head): if not head.next: # 空链表肯定不存在环 return None # 直接返回False 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
本文代码思路部分来自书籍《Python程序员面试宝典》，书中部分代码有问题或未提供代码，文中已经修改过了，并添加上了丰厚的注释，方便大家学习，后面我会把所有内容开源放到Github上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。希望大家多多支持。大家好，我是老表
觉得本文不错的话，转发、留言、点赞，是对我最大的支持。
