Smaller And Smarter Python数据结构:删除无序链表重复结点

简介: Smaller And Smarter Python数据结构:删除无序链表重复结点

简说Python,号主老表,Python终身学习者,数据分析爱好者,从18年开始分享Python知识,原创文章227篇,写过Python、SQL、Excel入门文章,也写过Web开发、数据分析文章,老表还总结整理了一份2022Python学习资料和电子书资源,关注后私信回复:2022 即可领取。

今天给大家分享的书籍《Python程序员面试算法宝典》第一章第二小节:删除无序链表重复结点。

如果你是第一次看,也许,你可以看看本系列下面的文章:

Smaller And Smarter Python数据结构:链表逆转

今日问题

"""
目标:写一段程序,从无序链表中移除重复项
例如:
输入-> 1->0->3->1->4->5->1->8
输出-> 1->0->3->4->5->8
"""
"""
Goal: write a program to remove duplicates from the unordered list
For example:
Input - > 1 - > 0 - > 3 - > 1 - > 4 - > 5 - > 1 - > 8
Output - > 1 - > 0 - > 3 - > 4 - > 5 - > 8
"""

首先我们写好链表的基本操作,在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

解题

开始程序前需提前导入前面写好的链表基本操作包a_0_base

from Linked_list.a_0_base import ListOperation
方法一:递归去重
"""
Method One : 递归去重
核心思想:每次遍历去重前,都先对子链表进行去重处理,
这样去重的子链表都会产生一个子链表,直到递归到尾结
点,此时开始回溯,每次回溯,会完成一个子链的去重,
直到回溯到头结点,链表去重完成。
时间复杂度:O(N^2)
空间复杂度:O(1)
"""
代码
def remove_duplicates_one(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    if not head.next:  # 空链表或者遍历到最后一个结点
        return head  # 返回头结点或者开始回溯
    cur_node = head  # 记录头结点
    head.next = remove_duplicates_one(head.next)   # 递归,往后遍历
    # print("此时cur_node=", cur_node.data)
    # print("此时head=", head.data)
    pointer = head.next  # 记录后继结点
    # print("此时pointer=", pointer.data)
    # 遍历查找
    while pointer:   # 遍历当前子链表
        if head.data == pointer.data:
            cur_node.next = pointer.next  # 删除相同结点
            pointer = cur_node.next  # 后移,遍历子链表
        else:
            pointer = pointer.next  # 后移,遍历子链表
            cur_node = cur_node.next  # 当前结点后移
    # print("此时head=", head.data)
    # print("____________________________")
    return head  # 返回当前子链表头结点
方法二:顺序删除
"""
Method Two : 顺序删除
核心思想:你要是搞清楚方法一,这个就不难理解了。
直接利用双循环,一个慢指针,一个快指针,匹配到
快慢指针的数据值相同时就删除该快指针,然后继续
遍历快指针,直至结束,然后慢指针后移,继续遍历。
时间复杂度:O(N^2)
空间复杂度:O(1)
"""
代码
def remove_duplicates_two(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    if not head.next:  # 空链表或者遍历到最后一个结点
        return head  # 返回头结点或者开始回溯
    slow_node = head.next  # 记录慢指针(外层循环)
    while slow_node:  # 外层遍历
        fast_node = slow_node.next  # 记录快指针(内层遍历)
        cur_node = slow_node  # 记录当前结点,方便删除结点
        while fast_node:  # 内层遍历
            if fast_node.data == slow_node.data:  # 在子链中查找值与slow_node一样的结点(值重复结点)
                cur_node.next = fast_node.next  # 删除重复结点(让当前结点的next指向重复结点的next)
            else:
                cur_node = fast_node  # 当前结点后移,继续遍历子链
            fast_node = fast_node.next  # 后移,继续遍历子链(快指针)
        slow_node = slow_node.next  # 后移,继续遍历(慢指针)
    return head  # 返回当前子链表头结点
方法三:空间换时间
"""
Method Three : 空间换时间
核心思想:建一个辅助栈记录链表数据项,遍历链表,
1、如果当前结点的数据项在辅助栈中,则删除该结点
2、如果当前结点数据项不在辅助栈中,则该结点数据项
进行入栈操作
3、继续遍历,直至遍历结束。
辅助栈可选数据类型:元祖,列表,字典,集合
其中字典和集合的查找时间复杂度为O(1),字典内部是有哈希表
(哈希函数+哈希冲突表)构成,故查找时间复杂度为O(1),
Python里集合的内部实现是字典,故查找时间复杂度也为O(1)。
时间复杂度:O(N)
空间复杂度:O(N)
"""
代码
def remove_duplicates_three(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    if not head.next:  # 空链表或者遍历到最后一个结点
        return head  # 返回头结点或者开始回溯
    run_node = head.next.next  # 从第二个结点开始遍历(因为第一个结点肯定不存在重复问题)
    pre_node = head.next  # 记录第一个结点,后面做前驱结点
    dict_all = {pre_node.data: "node"}  # 直接把第一个结点数据项加入字典,键值任意给
    while run_node:  # 遍历链表
        if run_node.data in dict_all:  # 判断当前遍历结点值在不在字典中
            pre_node.next = run_node.next  # 删除重复结点(让当前结点的next指向重复结点的next)
        else:  # 不在字典中,则入栈,并让前驱结点后移
            dict_all[run_node.data] = "node"
            pre_node = run_node
        run_node = run_node.next  # 后移遍历
    # print(dict_all)
    return head  # 返回当前子链表头结点

测试代码

# 当然,也许还有别的方法,比如建一个辅助的链表
# 欢迎你说出你的想法
# 程序入口,测试函数功能
if __name__ == "__main__":
    s0 = ListOperation()  # 初始化一个链表基本操作对象实例
    list_data = [1, 2, 3, 4, 2, 3, 9, 1]  # 链表初始化数据
    head = s0.init_list(list_data)  # 初始化链表,带头结点
    s0.ergodic_list(head)  # 未逆转前,遍历打印链表
    # head = remove_duplicates_one(head)  # 测试方法一,逆转链表
    # head = remove_duplicates_two(head)  # 测试方法二,逆转链表
    head = remove_duplicates_three(head)  # 测试方法三,逆转链表
    print("---------------------")
    s0.ergodic_list(head)  # 逆转后,遍历打印链表

本文代码思路来自书籍《Python程序员面试宝典》,书中部分代码有问题,文中已经修改过了,并添加上了丰厚的注释,方便大家学习,后面我会把所有内容开源放到Github上,包括代码,思路,算法图解(手绘或者电脑画),时间充裕的话,会录制视频。

希望大家多多支持。

大家好,我是老表

觉得本文不错的话,转发、留言、点赞,是对我最大的支持。

相关文章
|
2月前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
70 1
|
18天前
|
存储 索引 Python
Python编程数据结构的深入理解
深入理解 Python 中的数据结构是提高编程能力的重要途径。通过合理选择和使用数据结构,可以提高程序的效率和质量
131 59
|
18天前
|
存储 开发者 Python
Python 中的数据结构与其他编程语言数据结构的区别
不同编程语言都有其设计理念和应用场景,开发者需要根据具体需求和语言特点来选择合适的数据结构
|
18天前
|
存储 开发者 索引
Python 中常见的数据结构
这些数据结构各有特点和适用场景,在不同的编程任务中发挥着重要作用。开发者需要根据具体需求选择合适的数据结构,以提高程序的效率和性能
|
18天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
18天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
1月前
|
存储 算法 搜索推荐
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念,通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中,理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
18 1
|
2月前
|
存储 索引 Python
python数据结构之列表详解
列表是Python中极为灵活和强大的数据结构,适合于存储和操作有序数据集合。掌握其基本操作和高级特性对于编写高效、清晰的Python代码至关重要。通过本回答,希望能帮助你全面理解Python列表的使用方法,从而在实际编程中更加游刃有余。
34 0
|
13天前
|
人工智能 数据可视化 数据挖掘
探索Python编程:从基础到高级
在这篇文章中,我们将一起深入探索Python编程的世界。无论你是初学者还是有经验的程序员,都可以从中获得新的知识和技能。我们将从Python的基础语法开始,然后逐步过渡到更复杂的主题,如面向对象编程、异常处理和模块使用。最后,我们将通过一些实际的代码示例,来展示如何应用这些知识解决实际问题。让我们一起开启Python编程的旅程吧!
|
12天前
|
存储 数据采集 人工智能
Python编程入门:从零基础到实战应用
本文是一篇面向初学者的Python编程教程,旨在帮助读者从零开始学习Python编程语言。文章首先介绍了Python的基本概念和特点,然后通过一个简单的例子展示了如何编写Python代码。接下来,文章详细介绍了Python的数据类型、变量、运算符、控制结构、函数等基本语法知识。最后,文章通过一个实战项目——制作一个简单的计算器程序,帮助读者巩固所学知识并提高编程技能。