Smaller And Smarter Python数据结构:链表倒数第K个元素+检测单链表环

简介: Smaller And Smarter Python数据结构:链表倒数第K个元素+检测单链表环

简说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,可以领取精选编程学习电子书籍。

如果你觉得文章还不错,请大家点赞分享下。你的肯定是我最大的鼓励和支持。

相关文章
|
13天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
30 1
|
20天前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
22 7
|
20天前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
20 3
|
21天前
|
Python
Python 中常见的数据结构(二)
Python 中常见的数据结构(二)
16 4
|
18天前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
13 0
数据结构与算法学习五:双链表的增、删、改、查
|
21天前
|
存储 索引 Python
Python 中常见的数据结构(一)
Python 中常见的数据结构(一)
30 3
|
12天前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
16 0
|
14天前
|
存储 索引 Python
python数据结构之列表详解
列表是Python中极为灵活和强大的数据结构,适合于存储和操作有序数据集合。掌握其基本操作和高级特性对于编写高效、清晰的Python代码至关重要。通过本回答,希望能帮助你全面理解Python列表的使用方法,从而在实际编程中更加游刃有余。
13 0
|
18天前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
18天前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用