0%

LeetCode 面试题 02.01 移除重复节点

LeetCode 面试题 02.01移除重复节点

面试题 02.01 移除重复节点

题目详情

编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

1
2
输入:[1, 2, 3, 3, 2, 1]
输出:[1, 2, 3]

示例2:

1
2
输入:[1, 1, 1, 1, 2]
输出:[1, 2]

提示:

1
2
链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。

题解

需要对这个没有被排序的链表进行处理,删掉所有数值重复的节点。首先最开始想到的方法是给这个链表进行排序,然后对按链表顺序进行判断,如果和前一个节点数值相同了就把这个节点丢掉。

但是在提示里看到了链表的元素在[0,20000]内,链表元素的范围都给我们了,直接桶排序做就行了。新建一个大小为20000+5的数组,从头遍历每个节点,以节点的数值作为数组的索引,节点的数值如果在数组中为true(也就是之前出现过了),就可以跳过这个节点,没出现就更新对应数值为true

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
//ListNode结构是常规的val 以及next指向下一个Node
class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
//在测试样例中第二个样例就是head节点直接是Null,所以我们需要在最开始进行判断。
//如果head直接为Null就直接返回head,不然后面访问head.val会报错。
if(head==null){
return head;
}
//新建一个比范围大一点点的数组,建立桶
boolean []elements = new boolean[20005];
//建立一个temp节点用来指向当前访问到哪个位置了
ListNode temp = new ListNode(0);
temp=head;
elements[head.val]=true;
//不断遍历这条链表,直到访问位的下一位为Null
while(temp.next!=null){
//如果创建的桶里,没有这个节点的数值,就更新这个数值
if(!elements[temp.next.val]){
elements[temp.next.val]=true;
temp=temp.next;
}
//如果桶里有这个数值了,就可以把这个节点丢掉了(下一个节点指针指向下个节点的下个节点)。
else {
temp.next=temp.next.next;
}
}
return head;
}
}

提交后用时1ms,内存42.7MB,没办法,用桶排序肯定是空间换时间的。




======================
全 文 结 束    感 谢 阅 读
======================