重整旗鼓的首要步骤是停止做那些已经做错了的事。——巴菲特
题目：给定一个无序链表，例如：head->1->2>1-->3->3->5->7->6>7->8,删除其中的重复项，将其变成head->1->2->5->7->6->8。
我们先看一下这个无序链表怎么弄出来，总不能一个一个键盘敲进去吧！
这里我们要引入一个python自带的random库了，利用随机数生成一个无序链表：
#先引入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
这样输出的链表就是一个无序的链表了，而且会出现重复的节点值了。下面我们来分析一下如何实现题目的要求：题目要求我们删除链表的重复项，那么如何删除节点呢？我们可以把要删除的节点的前驱节点的next域指向当前节点的后继节点，如下图所示：
删除节点3的方法
方法有了，现在我们来实现它。就上图来说，假如当你遍历到节点3时，即cur指向3，你发现前面已经有3了，那就要删除它，按前面的方法：将节点1的next域指向节点7，这时你需要一个指向节点3的前驱节点的指针——pre来操作节点你1(因为单链表只能顺着链表遍历),所以代码实现为：
pre.next=cur.next # 这一句就可以删除cur节点
cur=pre.next # 遍历下一个节点
当然为了更好理解，也可以加一个Next指针指向当前节点的后继节点：
pre.next=Next # 这就非常直观了
cur=Next # 遍历下一个节点
还有，你也可以这么写：
pre.next=pre.next.next #
cur=pre.next # 遍历下一个节点
以上三种都是一个意思，都可以删除当前节点cur，第二种要多用一个空间来保存Next。
好的，删除节点的方法有了，下面就是如何判断是否是重复项:今天我们先介绍最容易想到的方法，那就是我先遍历一遍链表，在遍历每一个节点时，都再遍历一遍其子链表是否有与当前节点data值相同的节点，如果有就删除重复的节点，然后继续遍历子链表，直到子链表为空；然后再遍历下一个节点直到链表为空。从上面的分析可以看出，我们需要一个outerCur来遍历最外层的链表，还要有一个innerCur来遍历Outercur的子链表。下面我们来实现这个算法：
def removeDup(head):
"""
有头节点
"""
#先判断链表是否为空
if head.next is None or head is None:
return head
outerCur=head.next # 用于遍历整个链表
innerCur=None # 用于遍历当前节点的子链表
innerPre=None # 用于保存内部遍历的当前节点的前驱节点
while outerCur is not None:
#inner指向当前节点的后后继节点 用于遍历
innerCur=outerCur.next
#innerpre 用来保存当前节点的前驱节点
innerPre=outerCur
#这里开始内部遍历，直到链表为空
while innerCur is not None:
#判断内部遍历的当前节点的值是否与外部遍历的当前节点的值相同
if innerCur.data == outerCur.data:
#相同则删除节点
innerPre.next=innerCur.next
innerCur=innerCur.next
else:
#不同则继续遍历下一个节点，直到子链表为空
innerPre=innerCur
innerCur=innerCur.next
#遍历下一个节点
outerCur=outerCur.next
#返回处理完成的链表
return head
这就是顺序删除的算法实现(哇！我写的注释真清楚！没人夸，自己夸一下)
下面我们来验证一下这个算法是否可以完成题目要求:
if __name__ == '__main__':
#构造链表
head=construstLink(8)
#打印函数
print("Before-removeDup-head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
#调用函数
head=removeDup(head)
#查看完成后的链表
print("After-removeDup-head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
运行结果：
成功的移除了0和6！
下面是全部的代码：
#先引入random库
import random
class LNode(object):
"""docstring for LNode"""
def __init__(self, arg):
self.data = arg
self.next = None
"""
题目描述：
将Head->1->1->3->3->5->7->7->8变
为head->1->2->5->7->8
方法：顺序删除
"""
#这里!前几篇的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
def removeDup(head):
"""
有头节点
"""
#先判断链表是否为空
if head.next is None or head is None:
return head
outerCur=head.next # 用于遍历整个链表
innerCur=None # 用于遍历当前节点的子链表
innerPre=None # 用于保存内部遍历的当前节点的前驱节点
while outerCur is not None:
#inner指向当前节点的后后继节点 用于遍历
innerCur=outerCur.next
#innerpre 用来保存当前节点的前驱节点
innerPre=outerCur
#这里开始内部遍历，直到链表为空
while innerCur is not None:
#判断内部遍历的当前节点的值是否与外部遍历的当前节点的值相同
if innerCur.data == outerCur.data:
#相同则删除节点
innerPre.next=innerCur.next
innerCur=innerCur.next
else:
#不同则继续遍历下一个节点，直到子链表为空
innerPre=innerCur
innerCur=innerCur.next
#遍历下一个节点
outerCur=outerCur.next
#返回处理完成的链表
return head
if __name__ == '__main__':
#构造链表
head=construstLink(8)
#打印函数
print("Before-removeDup-head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
#调用函数
head=removeDup(head)
#查看完成后的链表
print("After-removeDup-head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
好的，今天的算法到这里就结束了，下面我又要说些废话了：学习不是一蹴而就的，虽然python语法简单，也不是说会了就会的，还是要自己多写代码，起码你不能连输入一个return "我真聪明"if random.randint(0, 6) == 1 else "我是一头蠢猪"都要敲半天，还看不懂什么意思！以后有时间我会写一些入门学Python的文章，当然网上的教程太多了，这里推荐大家去廖雪峰的网站学，教程很清楚，我就是跟着学的！！！
再我的github有所有的代码，当然可能会有所出入，但相差不多，欢迎大家学习！
这是我微信公众号：Dkider 方便大家联系我，当然也不会有太多人会联系我，就像那句话——我只是需要被需要，我很乐意为大家解决问题。
长按识别二维码
Dkider
没时间找诗了，就不写了
网友评论