简说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上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。
希望大家多多支持。
大家好，我是老表
觉得本文不错的话，转发、留言、点赞，是对我最大的支持。
