原创： 老表 简说Python

今日问题 ：单链表中的倒数第k个元素

"""目标：写一段程序，找出单链表中的倒数第k个元素例如：输入 k = 3输入-> 1->2->6->4->5输出 6Goal: write a program to find the last K element in the single linked listFor example:Input k = 3Input - > 1 - > 2 - > 6 - > 4 - > 5Output 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 = Noneclass 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)"""

代码

def find_last_k_three(head, k): if not head.next: # 遍历到尾结点 return head, k # 返回尾结点和k值 result_node = head.next # 向后递归 # print(k) cur_node, k = find_last_k_three(result_node, k) # 递归 k = k - 1 # 记录回溯次数 # print("k = %d" % k) if k == 0: # 当k等于0时，说明已经回溯到了倒数第k个结点 cur_node = result_node # 从后往前，第k个结点 return cur_node, k # 返回倒数第k个结点

测试代码

# 当然，也许还有别的方法，比如建一个辅助的链表# 欢迎你说出你的想法# 程序入口，测试函数功能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 (表示结点地址)输出 环结点：2Goal: write a program to check whether a large single chain table has ringsFor 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 = Noneclass 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上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。

最后，我自己是一名从事了多年开发的Python老程序员，辞职目前在做自己的Python私人定制课程，今年年初我花了一个月整理了一份最适合2019年学习的Python学习干货，可以送给每一位喜欢Python的小伙伴，想要获取的可以关注我的头条号并在后台私信我：01，即可免费获取。