删除单链表中重复的值（Java版）

浏览数：61 / 时间：2015年06月08日

题目：删除带头结点的单链表中重复值的元素(即让每种值的元素只有一个)

解题思路：

用一个动态辅助存储数组，每次要向辅助数组中放入元素时，让辅助数组的长度加1，最长时与单链表一样长，设一个指针p，让它指向头结点，从单链表中第一个元素开始，将它的值放入辅助数组中，然后依次访问单链表后面的元素，用该元素的值与数组中所有已经被赋值的元素的值进行比较，如果不等于数组中任何元素的值，那么让p的next指向该结点的next指针，删除该结点元素，否则令p指向p的next指针，并将当前访问的节点元素的值依次放入辅助数组，一直访问到单链表中的最后一个元素。

ADT定义：

//单链表的结点类
class LNode{
	//为了简化访问单链表，结点中的数据项的访问权限都设为public
	public int data;
	public LNode next;
}

算法实现：

public class LinkListUtli {
	public static void deleteRepeatValue(LNode L)
	{
		//如果单链表为空，或者只有头结点，或者头结点后面只有一个元素时，不可能存在值重复的元素
		if(L==null||L.next==null||L.next.next==null) return;
		LNode p=L;//当前访问结点的前一个结点
		LNode q=L.next;//当前访问的结点
		int count=0;
		while(q!=null){
			count++;
		}
		int temp[]=new int[count];
		count=1;
		temp[count-1]=q.data;
		while(q.next!=null)//一直往下访问，直到访问单链表中的最后一个结点
		{
			q=q.next;//访问下一个结点
			boolean flag=false;//用来标记当前访问结点元素中的值是否与之前访问结点元素的值相同
			for(int i=0;i<count;i++)
			{
				if(q.data==temp[i])
				{
					p.next=q.next;
					flag=true;
					break;
				}
			}
			if(!flag)
			{
				count++;	
				temp[count-1]=q.data;
				q=q.next;//让q往下走一步,保证p是下个访问结点的前一个结点
			}
		}
		q=null;//此时q可能是已经释放了的指针，如果不令它指向null，它会变成野指针
	}
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

删除单链表中重复的值（Java版）