简说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数据结构：合并两个有序链表
今日问题 ：单链表删除给定结点，而且只给该结点
""" 目标：写一段程序，删除给定结点，而且只给该结点 例如： 初始化链表-> 1->2->3->4->5->6 输入 结点 3 删除后链表-> 1->2->4->5->6 输出 给定结点3已删除 Goal: write a program, delete the given node, and only give the node For example: Initialize the list - > 1 - > 2 - > 3 - > 4 - > 5 - > 6 Input node 3 Delete the linked list - > 1 - > 2 - > 4 - > 5 - > 6 Output given node 3 deleted """
解题准备
首先我们写好链表的基本操作，在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 : 复制删除法 简单分析：因为题目只给了一个结点，然后要求是把这个结点从链表中删除， 一般我们要删除链表的一个结点，肯定是遍历找到这个结点的前驱结点，让 前驱结点指向该结点的后继结点即可，但，我们现在只有一个待删除的结点。 核心思路：比如给定链表p，如果p为尾结点，无法删除，因为找不到前驱结点， 否则，让p的数据域等于p.next的数据域，然后删除p.next结点。 时间复杂度：O(1) 空间复杂度：O(1) """
代码
def delete_given_node_one(p): if not p.next: # p为链表尾结点 return False # 无法删除 copy_node = p.next # 记录p结点下个结点 p.data = copy_node.data # 复制结点数据域 p.next = copy_node.next # 删除p结点下个结点 return True # 返回结果
测试代码
# 当然，也许还有别的方法，比如建一个辅助的链表 # 欢迎你说出你的想法 # 程序入口，测试函数功能 if __name__ == "__main__": list_data = [1, 2, 3, 4, 5, 6, 7] # 链表初始化数据 head = ListOperation.init_list(list_data) # 初始化链表，带头结点 ListOperation.ergodic_list(head) # 未操作前，遍历打印链表 p = ListOperation.get_random_node(head) # 获取一个随机结点 print("待删除结点数据域为：", p.data) result = delete_given_node_one(p) # 测试方法一 if result: print("结点已删除") else: print("尾结点无法删除") print("---------------------") ListOperation.ergodic_list(head) # 操作后，遍历打印链表
今日问题 ：判断两个单链表（无环）是否交叉，并找出交叉结点
""" 目标：写一段程序，判断两个单链表（无环）是否交叉，并找出交叉结点 例如： 输入-> A->B->C->D->5->6->7 输入-> 1->4->5->6->7 输出 5 Goal: Write a program to judge whether two single chain tables (acyclic) cross, and find out the cross node For example: Input - > A - > B - > C - > D - > 5 - > 6 - > 7 Input - > 1 - > 4 - > 5 - > 6 - > 7 Output 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: 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 : 借助辅助空间 核心思想：首先遍历链表1，将链表1的每个结点都存储到字典中，作为key, 然后遍历链表2，判断链表2中的结点是否在字典中，如果不存在，则两个链表 不相交，否则两个链表相交，相交结点即为链表2遍历到的结点。 不修改原始链表 时间复杂度：O(N) N = n1+n2 空间复杂度：O(n1) """
代码
def links_cross_one(head1, head2): # 有链表为空，则肯定不相交 if not head1.next: return None # 直接返回None if not head2.next: return None # 直接返回None cur_node1 = head1.next # 记录第一个结点，后面做前驱结点 dict_all = {cur_node1: "node"} # 直接把第一个结点加入字典 while cur_node1.next: # 遍历链表1，将结点加入字典 cur_node1 = cur_node1.next # 后移遍历 dict_all[cur_node1] = "node" # 将该结点加入字典 cur_node2 = head2.next while cur_node2: # 遍历链表2，判断是否相交 if cur_node2 in dict_all: # 判断遍历结点是否在字典中 return cur_node2 # 在字典中，则两链表相交，相交结点即为当前遍历到的结点 cur_node2 = cur_node2.next # 后移，继续遍历 return None # 遍历完成，没有触发相交判断，则说明不相交，返回None
方法二：首尾连接法
解题思路
""" Method Two ：首尾连接法 核心思想：将两个链表连接，然后判断连接后的链表是否存在环， 如果有环的话，说明两个链表是相交。 会修改原始链表 时间复杂度：O(N) N = n1 + n2 空间复杂度：O(1) """
代码
# 辅助函数：判断链表是否有环 def check_ring_two(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): 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 links_cross_two(head1, head2): # 有链表为空，则肯定不相交 if not head1.next: return None # 直接返回None if not head2.next: return None # 直接返回None cur_node = head1.next # 获取链表1的第一个结点 while cur_node.next: # 遍历链表1，找到链表1的尾结点 cur_node = cur_node.next # 后移遍历 cur_node.next = head2.next # 让链表1的尾结点指向链表2的第一个结点（连接链表1和链表2） # 第一步：检查是否有环 ring_is = check_ring_two(head1) if ring_is: # 有环说明原来链表相交 # 第二步：找出环的入口（即原两链表的相交结点） cross_node = get_ring_node(head1, ring_is) return cross_node # 返回找到的相交结点 return None # 不相交
方法三：尾结点法
解题思路
""" Method Three ：尾结点法 核心思想：如果两个链表相交，则尾结点必然相同（一画便知）， 所以可以先遍历两个链表，记录链表长度，比较尾结点是否相同， 不相同，则不相交，否则，两链表相交，再次遍历两链表，长链 表先出发(n1-n2)步，然后短链表也开始遍历，两链表遍历到结 点相同时，即为相交结点。 时间复杂度：O(N) 空间复杂度：O(1) """
代码
def links_cross_three(head1, head2): # 有链表为空，则肯定不相交 if not head1.next: return None # 直接返回None if not head2.next: return None # 直接返回None cur_node1 = head1.next # 获取链表1第一个结点 cur_node2 = head2.next # 获取链表2第一个结点 n1 = 1 # 记录链表1长度 n2 = 1 # 记录链表2长度 while cur_node1.next: # 遍历链表1 cur_node1 = cur_node1.next n1 = n1 + 1 while cur_node2.next: # 遍历链表2 cur_node2 = cur_node2.next n2 = n2 + 1 # print(n1,n2) if cur_node1 != cur_node2: # 链表1与链表2尾结点不一样 return None # 说明两个链表不相交 # 否则，两个链表相交 if n1 > n2: # 链表1长 while n1 - n2 > 0: # 链表长的先遍历 head1 = head1.next n1 = n1 - 1 else: # 链表2长 while n2 - n1 > 0: head2 = head2.next n2 = n2 - 1 # print(head1.data) # print(head2.data) while head1 != head2: # 一起遍历，查找相交结点 head1 = head1.next # 后移遍历 head2 = head2.next # 后移遍历 return head1 # 返回找到的相交结点
测试代码
# 当然，也许还有别的方法，比如建一个辅助的链表 # 欢迎你说出你的想法 # 程序入口，测试函数功能 if __name__ == "__main__": list_data1 = [1, 2, 3, 4, 5, 6, 7, 8] # 链表1初始化数据 list_data2 = ["A", "B", "C", "D"] # 链表2初始化数据 head1 = ListOperation.init_list(list_data1) # 初始化链表1，带头结点 head2 = ListOperation.get_random_link(list_data2, head1) # 初始化链表2，带头结点，与链表1相交 ListOperation.ergodic_list(head1) # 未操作前，遍历打印链表1 print("___________________________") ListOperation.ergodic_list(head2) # 未操作前，遍历打印链表2 # result = links_cross_one(head1, head2) # 测试方法一 # result = links_cross_two(head1, head2) # 测试方法二 result = links_cross_three(head1, head2) # 测试方法一 print("---------------------") if result: print("链表1与链表2相交，相交结点为：", result.data) else: print("链表1与链表2不相交")
本文代码思路部分来自书籍《Python程序员面试宝典》，书中部分代码有问题或未提供代码，文中已经修改过了，并添加上了丰厚的注释，方便大家学习，后面我会把所有内容开源放到Github上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。
希望大家多多支持。
大家好，我是老表
觉得本文不错的话，转发、留言、点赞，是对我最大的支持。
欢迎关注微信公众号：简说Python
关注后回复：1024，可以领取精选编程学习电子书籍。
如果你觉得文章还不错，请大家点赞分享下。你的肯定是我最大的鼓励和支持。
