python无序链表删除重复项的方法
题目描述:
给定一个没有排序的链表,去掉重复项,并保留原顺序如:1->3->1->5->5->7,去掉重复项后变为:1->3->5->7
方法:
- 顺序删除
- 递归删除
1.顺序删除
由于这种方法采用双重循环对链表进行遍历,因此,时间复杂度为O(n**2)
在遍历链表的过程中,使用了常数个额外的指针变量来保存当前遍历的结点,前驱结点和被删除的结点,所以空间复杂度为O(1)
#!/usr/bin/envpython3 #-*-coding:utf-8-*- #@Time:2020/1/1520:55 #@Author:buu #@Software:PyCharm #@Blog:https://blog.csdn.net/weixin_44321080 classLNode: def__init__(self,x): self.data=x self.next=None defremoveDup(head): """ 对带头结点的无序单链表删除重复的结点 顺序删除:通过双重循环直接在链表上进行删除操作 即,外层循环用一个指针从第一个结点开始遍历整个链表,内层循环从外层指针指向的下一个结点开始, 遍历其余结点,将与外层循环遍历到的的指针所指的结点的数据域相同的结点删除 :paramhead:头指针 :return: """ ifheadisNoneorhead.nextisNone: return outerCur=head.next innerCur=None innerPre=None whileouterCurisnotNone: innerCur=outerCur.next innerPre=outerCur whileinnerCurisnotNone: ifouterCur.data==innerCur.data: innerPre.next=innerCur.next innerCur=innerCur.next else: innerPre=innerCur innerCur=innerCur.next outerCur=outerCur.next if__name__=='__main__': i=1 head=LNode(6) tmp=None cur=head whilei<7: ifi%2==0: tmp=LNode(i+1) elifi%3==0: tmp=LNode(i-2) else: tmp=LNode(i) cur.next=tmp cur=tmp i+=1 print("beforeremoveDup:") cur=head.next whilecurisnotNone: print(cur.data,end='') cur=cur.next removeDup(head) print("\nafterremoveDup:") cur=head.next whilecurisnotNone: print(cur.data,end='') cur=cur.next
结果:
2.递归
此方法与方法一类似,从本质上而言,由于这种方法需要对链表进行双重遍历,所以时间复杂度为O(n**2)
由于递归法会增加许多额外的函数调用,所以从理论上讲,该方法效率比方法一低
#!/usr/bin/envpython3 #-*-coding:utf-8-*- #@Time:2020/1/1521:30 #@Author:buu #@Software:PyCharm #@Blog:https://blog.csdn.net/weixin_44321080 classLNode: def__init__(self,x): self.data=x self.next=None defremoveDupRecursion(head): """ 递归法:将问题逐步分解为小问题,即,对于结点cur,首先递归地删除以cur.next为首 的子链表中重复的结点;接着删除以cur为首的链表中的重复结点, :paramhead: :return: """ ifhead.nextisNone: returnhead pointer=None cur=head head.next=removeDupRecursion(head.next) pointer=head.next whilepointerisnotNone: ifhead.data==pointer.data: cur.next=pointer.next pointer=cur.next else: pointer=pointer.next cur=cur.next returnhead defremoveDup(head): """ 对带头结点的单链表删除重复结点 :paramhead:链表头结点 :return: """ ifheadisNone: return head.next=removeDupRecursion(head.next) if__name__=='__main__': i=1 head=LNode(6) tmp=None cur=head whilei<7: ifi%2==0: tmp=LNode(i+1) elifi%3==0: tmp=LNode(i-2) else: tmp=LNode(i) cur.next=tmp cur=tmp i+=1 print("beforerecursiveremoveDup:") cur=head.next whilecurisnotNone: print(cur.data,end='') cur=cur.next removeDup(head) print("\nafterrecurseveremoveDup:") cur=head.next whilecurisnotNone: print(cur.data,end='') cur=cur.next
结果:
引申:从有序链表中删除重复项
上述介绍的方法也适用于链表有序的情况,但是由于上述方法没有充分利用到链表有序这个条件,因此,算法的性能肯定不是最优的。本题中,由于链表具有有序性,因此不需要对链表进行两次遍历。所以有如下思路:
用cur指向链表的第一个结点,此时需要分为以下两种情况讨论:
- 如果cur.data==cur.next.data,则删除cur.next结点;
- 如果cur.data!=cur.next.data,则cur=cur.next,继续遍历其余结点;
总结
以上所述是小编给大家介绍的python无序链表删除重复项的方法,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。