方法一:顺序删除 主要思路为:通过双重循环直接在链表上进行删除操作。外层循环用一个指针从第一个结点开始遍历整个链表,然后内层循环用另外一个指针遍历其余结点,将与外层循环遍历到的指针所指结点的数据域相同的结点删除。如下图所示:
假设外层循环从outerCur开始遍历,当内层循环指针innerCur遍历到上图实线所示的位置(outerCur.data==innerCur.data)时,此时需要把innerCur指向的结点删除。具体步骤如下:
(1)用tmp记录待删除的结点的地址。
(2)为了能够在删除tmp结点后继续遍历链表中其余的结点,使innerCur指向它的后继结点:innerCur=innerCur.next。
(3)从链表中删除tmp结点。
实现代码如下:
package main
import(
"fmt"
."github.com/isdamir/gotype" //引入定义的数据结构
)
//顺序删除
func RemovDup(head*LNode){
if head==nil || head.Next==nil {
return
}
outerCur:=head.Next //用于外层循环,指向链表第一个结点
var innerCur*LNode //用于内层循环遍历ourterCur后面的结点
var innerPre*LNode //innerCur的前驱结点
for; outerCur!=nil; outerCur=outerCur.Next{
forinnerCur, innerPre=outerCur.Next, outerCur; innerCur!=nil; {
if(outerCur.Data=innerCur.Data){
innerPre.Next=innerCur.Next
innerCur=innerCur.Next
}else{
innerPre=innerCur
innerCur=innerCur.Next
}
}
}
}
func main(){
head:=&LNode{}
fmt.Println("删除重复结点")
CreateNodeT(head)
fmt.Println("——顺序删除——")
PrintNode("删除重复结点前:", head)
RemovDup(head)
PrintNode("删除重复结点后:", head)
CreateNodeT(head)
}
程序的运行结果为
删除重复结点前:1 3 1 5 5 7
删除重复结点后:1 3 5 7
算法性能分析: 由于这种方法采用双重循环对链表进行遍历,因此,时间复杂度为O(n
2),其中,N为链表的长度,在遍历链表的过程中,使用了常量个额外的指针变量来保存当前遍历的结点、前驱结点和被删除的结点,因此,空间复杂度为O(1)。
方法二:递归法 主要思路为:对于结点cur,首先递归地删除以cur.next为首的子链表中重复的结点,接着从以cur.next为首的子链表中找出与cur有着相同数据域的结点并删除,实现代码如下:
//递归法
func removeDupRecursionChild(head*LNode)*LNode{
if head==nil || head.Next==nil{
return head
}
vat pointer*LNode
cur:=head
//对以head.Next为首的子链表删除重复的结点
head.Next=removeDupRecursionChild(head.Next)
pointer=head.Next
//找出以以head.Next为首的子链表中与head结点相同的结点并删除
for pointer!=nil{
if(head.Data==pointer.Data){
cur.Next=pointer.Next
pointer=cur.Next
}else{
pointer=pointer.Next
cur=cur.Next
}
}
return head
}
func RemoVeDupRecursion(head*LNode){
if(head==nil){
return
}
head.Next=removeDupRecursionChild(head.Next)
}
算法性能分析: 这种方法与方法一类似,从本质上而言,由于这种方法需要对链表进行双重遍历,因此,时间复杂度为O(n
2),其中,N为链表的长度。由于递归法会增加许多额外的函数调用,因此,从理论上讲,该方法效率比方法一低。
方法三:空间换时间 通常情况下,为了降低时间复杂度,往往在条件允许的情况下,通过使用辅助空间实现。具体而言,主要思路为:
(1)建立一个HashSet,HashSet中的内容为已经遍历过的结点内容,并将其初始化为空。
(2)从头开始遍历链表中的所以结点,存在以下两种可能性:
1)如果结点内容已经在HashSet中,则删除此结点,继续向后遍历。
2)如果结点内容不在HashSet中,则保留此结点,将词结点内容添加到HashSet中,继续向后遍历。