方法一:顺序删除 主要思路为:通过双重循环直接在链表上进行删除操作。外层循环用一个指针从第一个结点开始遍历整个链表,然后内层循环用另外一个指针遍历其余结点,将与外层循环遍历到的指针所指结点的数据域相同的结点删除。如下图所示:
假设外层循环从outerCur开始遍历,当内层循环指针innerCur遍历到上图实线所示的位置(outerCur.data==innerCur.data)时,此时需要把innerCur指向的结点删除。具体步骤如下:
1)用tmp记录待删除的结点的地址;
2)为了能够在删除tmp结点后继续遍历链表中其余的结点,使innerCur指向它的后继结点:innerCur=innerCur.next。
3)从链表中删除tmp结点。
实现代码如下:
public class Test
{
//
//方法功能:对带头结点的无序单链表删除重复的结点
//输入参数:head:指向链表头结点
//
public static void RemoveDup(LNode head)
{
if(head==null||head.next==null)
return;
LNode outerCur=head.next;//外层循环指针,指向链表第一个结点
LNode innerCur=null;//内层循环用来遍历ourterCur后面的结点
LNode innerPre=null; //innerCur的前驱结点
for(; outerChr!=null; outerCur=outerCur.next)
{
for(innerCur=outerCur.next,innerPre=outerCur;innerCur!=null;)
{
//找到重复的结点并删除
if(outerCur.data==innerCur.data){
innerPre.next=innerCur.next;
innerCur=innerCur.next;
}else{
innerPre=innerCur;
innerCur=innerCur.next;
}
}
}
}
public static void Main(String[] args)
{
int i=1;
//链表头指针
LNode head=new LNode();
head.next=null;
LNode tmp=null;
LNode cur=head;
for(;i=7;i++){
tmp=new LNode();
if(i%2==0)
tmp.data=i+1;
else if(i % 3==0)
tmp.data=i-2;
else
tmp.data= i;
tmp.next=null;
cur.next=tmp;
cur=tmp;
}
Console.Write("删除重复结点前:");
for(cur=head.next; cur!=null; cur=cur.next)
Console.Write(cur.data+"");
RemoveDup(head);
Console.Write("\n删除重结点后:");
for(cur=head.next; cur!=null;cur=cur.next)
Console.Write(cur.data+" ");
}
}
程序的运行结果为
删除重复结点前:1 3 1 5 5 7
删除重复结点后:1 3 5 7
算法性能分析: 由于这个算法采用双重循环对链表进行遍历,因此,时间复杂度为O(n
2),其中,n为链表的长度,在遍历链表的过程中,使用了常量个额外的指针变量来保存当前遍历的结点、前驱结点和被删除的结点,因此,空间复杂度为O(l)。
方法二:递归法 主要思路为:对于结点cur,首先递归地删除以cur.next为首的子链表中重复的结点,接着从以cur.next为首的子链表中找出与cur有着相同数据域的结点并删除,实现代码如下:
private static LNode removeDupRecursion(LNode head)
{
if(head.next==null)
return head;
LNode pointer=null;
LNode cur=head;
//对以head.next为首的子链表删除重复的结点
head.next=removeDupRecursion(head.next);
pointer=head.next;
//找出以head.next为首的子链表中与head结点相同的结点并删除
while(pointer!=null)
{
if(head.data==pointer.data)
{
cur.next=pointer.next;
pointer=cur.next;
} else
{
pointer=pointer.next;
cur=cur.next;
}
}
return head;
}
//
//方法功能:对带头结点的单链删除重复结点输入参数:head:指向链表头结点
//
public static void RemoveDup(LNode head)
{
if (head==null)
return;
head.next=RemoveDupRecursion(head.next);
}
用方法一中的Main函数运行这个方法可以得到相同的运行结果。
算法性能分析: 这个方法与方法一类似,从本质上而言,由于这个方法需要对链表进行双重遍历,因此,时间复杂度为O(n
2),其中,n为链表的长度。由于递归法会增加许多额外的函数调用,因此,从理论上讲,该方法效率比方法一低。
方法三:空间换时间 通常情况下,为了降低时间复杂度,往往在条件允许的情况下,通过使用辅助空间实现。具体而言,主要思路为:
1)建立一个HashSet,HashSet中的内容为已经遍历过的结点内容,并将其初始化为空。
2)从头开始遍历链表中的所以结点,存在以下两种可能性:
①如果结点内容已经在HashSet中,则删除此结点,继续向后遍历。
②如果结点内容不在HashSet中,则保留此结点,将此结点内容添加到HashSet中,继续向后遍历。
引申:如何从有序链表中移除重复项 分析与解答: 上述介绍的方法也适用于链表有序的情况,但是由于以上方法没有充分利用到链表有序这个条件,因此,算法的性能肯定不是最优的。本题中,由于链表具有有序性,因此,不需要对链表进行两次遍历。所以,有如下思路:用cur指向链表第一个结点,此时需要分为以下两种情况讨论:
1)如果cur.data==cur.next.data,那么删除cur.next结点;
2)如果cur.data!=cur.next.data,那么cur=cur.next,继续遍历其余结点。