document.write('方法一：顺序删除
主要思路为：通过双重循环直接在链表上进行删除操作。外层循环用一个指针从第一个结点开始遍历
整个链表，然后内层循环用另外一个指针遍历其余结点，将与外层循环遍历到的指针所指结点的数据域
相同的结点删除。如下图所示：
假设外层循环从outerCur开始遍历，当内层循环指针innerCur遍历到上图实线所示的位置
(outerCur.data= =innerCur.data)时，需要把innerCur指向的结点删除。具体步骤如下：
(1)用tmp记录待删除的结点的地址。
(2)为了能够在删除tmp结点后继续遍历链表中其余的结点，使innerCur指向它的后继结点：
innerCUFinnerCur.next。
(3)从链表中删除tmp结点。
实现代码如下：
class LNode:
def __new__(self,x):
self.data=x
self.next=None
"""
** 方法功能: 对带头结点的无序单链表删除重复的结点
** 输入参数: head:链表头结点
"""
def removeDup(head):
if head==None or head.next==None:
return
outerCur=head.next # 用于外层循环, 指向链表第一个结点
innerCur=None # 用于内层循环用来遍历outerCur后面的结点
innerPre=None # innerCur的前驱结点
while outerCur!=None:
innerCur=outerCur.next
innerPre=outerCur
while innerCur!=None:
# 找到重复的结点并删除
if outerCur.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()
head.next=None
tmp=None
cur=head
while i＜7:
tmp=LNode()
if i%2=0:
tmp.data=i+1
elif i%3=0:
tmp.data=i-2
else:
tmp.data=i
tmp.next=None
cur.next=tmp
cur=tmp
i+=1
print "删除重复结点前:",
cur=head.next
while cur!=None:
print cur.data,
cur=cur.next
removeDup(head)
print "\\n删除重复结点后:",
cur=head.next
while cur!=None:
print cur.data,
cur=cur.next
程序的运行结果为：
删除重复结点前：1 3 1 5 5 7
删除重复结点后：1 3 5 7
算法性能分析：
由于这种方法采用双重循环对链表进行遍历，因此，时间复杂度为O(N2
)，其中，N为链表的长度，
在遍历链表的过程中，使用了常量个额外的指针变量来保存当前遍历的结点、前驱结点和被删除的结
点，因此，空间复杂度为O(1)。
方法二：递归法
主要思路为：对于结点cur，首先递归地删除以cur.next为首的子链表中重复的结点，接着从以
cur.next为首的子链表中找出与cur有着相同数据域的结点并删除，实现代码如下：
def removeDupRecursion(head):
if head.next is None:
return head
pointer=None
cur=head
#对以head.next为首的予链表删除重复的结点
head.next=removeDupRecursion(head.next)
pointer=head.next
#找出以head.next为首的子链表中与head结点相同的结点并删除
while pointeris not None:
if head.data=pointer.data:
cur.next=pointer.next
pointer=cur.next
else:
pointer=pointer.next
cur=cur.next
return head
"""
方法功能: 对带头结点的单链删除重复结点输入参数: head:链表头结点
"""
def removeDup(head):
if (head is None):
return
head.next=removeDupRecursion(head.next)
算法性能分析：
这种方法与方法一类似，从本质上而言，由于这种方法需要对链表进行双重遍历，因此，时间复杂度
为O(N2
)，其中，N为链表的长度。由于递归法会增加许多额外的函数调用，因此，从理论上讲，该方
法效率比方法一低。
方法三：空间换时间
通常情况下，为了降低时间复杂度，往往在条件允许的情况下，通过使用辅助空间来实现。具体而
言，主要思路为：
(1)建立一个HashSet，HashSet中的内容为已经遍历过的结点内容，并将其初始化为空。
(2)从头开始遍历链表中的所有结点，存在以下两种可能性：
1)如果结点内容已经在HashSet中，那么删除此结点，继续向后遍历。
2)如果结点内容不在HashSet中，那么保留此结点，将此结点内容添加到HashSet中，继续向后遍历。
');
![\"360截图20190815224632781.jpg\"](\"http://www.alatiku.com/d/file/shiti/efc6df9f925f275480bf57358b712e84.jpg\")