微信

使用微信服务,更方便

职友集>程序员面试题 > 删除单链表中重复的元素

删除单链表中重复的元素

2015-02-06 06:30:01 阅读( 60 )

1299人 收藏本页

标签:程序员面试题

用Hashtable辅助,遍历一遍单链表就能搞定。
实践中发现,curr从表头开始,每次判断下一个元素curr.Netx是否重复,如果重复直接使用curr.Next = curr.Next.Next; 就可以删除重复元素——这是最好的算法。唯一的例外就是表尾,所以到达表尾,就break跳出while循环。
public static Link DeleteDuplexElements(Link head)
{
Hashtable ht = new Hashtable();
Link curr = head;
while (curr != null)
{
if (curr.Next == null)
{
break;
}
if (ht[curr.Next.Data] != null)
{
curr.Next = curr.Next.Next;
}
else
{
ht[curr.Next.Data] = “”;
}
curr = curr.Next;
}
return head;
}
结语:
单链表只有一个向前指针Next,所以要使用1-2个额外变量来存储当前元素的前一个或后一个指针。
尽量用while循环而不要用for循环,来进行遍历。
哇塞,我就是不用指针,照样能“修改地址”,达到和C++同样的效果,虽然很烦~
遍历的时候,不要在while循环中head=head.Next;这样会改变原先的数据结构。我们要这么写:Link curr=head;然后curr=curr.Next;
有时我们需要临时把环切开,有时我们需要临时把单链表首尾相连成一个环。
究竟是玩curr还是curr.Next,根据不同题目而各有用武之地,没有定论,不必强求。

来自分智网

下一篇:栈和队列

上一篇:用链表模拟大整数加法运算

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题