python算法-007从无序链表中移除重复项（递归法）
我一生最大的功劳，就是保住了钱钟书的淘气和那一团痴气，让钱钟书的天性没有受到压迫，没有受到损伤。——杨绛
真好！
今天电脑出问题了，现在在一个安装在U盘中的ubuntu里，写这个文章，时间仓促，见谅！
题目：题目：给定一个无序链表，例如：head->1->2>1-->3->3->5->7->6>7->8,删除其中的重复项，将其变成head->1->2->5->7->6->8。
昨天介绍的利用HashSet集合，成功的解决了上面的问题，而且时间复杂度降到了O(N)，因为这种方法只需要遍历一次。之前我们也用了顺序删除的方法，也完成了题目的要求。那么之前将讲过的递归是否能解决这个问题呢？下面我们一起来看一下：
解决这个问题主要分为两个主要步骤：1）判断当前节点是否重复出现过；2）删除节点。至于删除节点前面讲过了——删除节点。顺序删除法是通过内外两层循环，判断内循环是否存在外循环遍历的节点；HashSet法是利用了python集合的特性。递归程序的两个要素之前强调过了——递归定义与递归终止条件。主要思路为：遍历链表，并删除其子链表中与当前节点cur数据域相同的节点，然后删除cur.next的子链表中与其数据域相同的节点。
下面是算法代码：
"""
题目描述：
将Head->1->1->3->3->5->7->7->8变
为head->1->2->5->7->8
方法：递归法2
"""
def RemoveDup(head):
if head.next is None:
return head
#这里的if语句只是为了判断递归是否到了最后第二个节点，所以下面不需要else语句
#直接写在if同一层就行。
pre=head#
cur=head.next
head.next=RemoveDup(head.next)
# 注意是head.next 因为这里是去掉与head相同的值，但是head还是留下来的
while cur is not None:
if cur.data == head.data:
pre.next=cur.next
cur=cur.next
#删除重复节点的操作：
# ___________________________
# / \
# | V
# 1 -----> 1 -----> 2
# ^ ^
# | |
# pre cur
# 这不知道你们能不能看懂。。。。
else:
#遍历下一个节点
cur=cur.next
pre=pre.next
return head
构造无序链表：
#先引入random库
import random
#依然是先定义节点类
class LNode(object):
def __init__(self, arg):
self.data = arg
self.next = None
#这里!前几篇的create我写错了，少了个e,
#这里改用construct 构造的意思
def construstLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
#这里与之前不同，先生成一个随机数，作为节点值
n = random.randint(0, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
return head
主程序：
if __name__ == '__main__':
#构造链表
head=construstLink(10)
#打印处理之前的链表
print("BeforeReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
#调用算法，处理链表
head = RemoveDup(head)
# 打印处理之后的链表
print("\nAfterReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
运行结果(linux)：
结果正确
全部代码：
#先引入random库
import random
#依然是先定义节点类
class LNode(object):
def __init__(self, arg):
self.data = arg
self.next = None
#这里!前几篇的create我写错了，少了个e,
#这里改用construct 构造的意思
def construstLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
#这里与之前不同，先生成一个随机数，作为节点值
n = random.randint(0, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
return head
"""
题目描述：
将Head->1->1->3->3->5->7->7->8变
为head->1->2->5->7->8
方法：递归法2
"""
def RemoveDup(head):
if head.next is None:
return head
#这里的if语句只是为了判断递归是否到了最后第二个节点，所以下面不需要else语句
#直接写在if同一层就行。
pre=head#
cur=head.next
head.next=RemoveDup(head.next)
# 注意是head.next 因为这里是去掉与head相同的值，但是head还是留下来的
while cur is not None:
if cur.data == head.data:
pre.next=cur.next
cur=cur.next
#删除重复节点的操作：
# pre cur
# | |
# |______|______
# \ >
# \ /
# \_________/这不知道你们能不能看懂。。。。
#这里在微信显示不太正常，网页，app内是正常的
else:
#遍历下一个节点
cur=cur.next
pre=pre.next
return head
if __name__ == '__main__':
#构造链表
head=construstLink(10)
#打印处理之前的链表
print("BeforeReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
#调用算法，处理链表
head = RemoveDup(head)
# 打印处理之后的链表
print("\nAfterReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
好的，今天的算法就到这，因为电脑原因，原来准备好的程序暂时没找到，现写的会出问题（老师讲的）而且注释并不太全，不过我也尽力写上了。还有，这个老师还说：程序算法最好用流程图表示出来，写程序前写程序后都要，这是一个好习惯，可以让大家更好的理解算法。所以过几天，会开始在分析算法时将流程图贴出来，让我们更好的理解。当然这一切都得等我电脑弄好了。（linux真好看）
是个狠人！
整个清华没有一个教授有资格充当钱某人的导师！——钱钟书说于清华大学
人谓我狂，不知我实狷。——钱钟书
