Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?
Hint
- Have you tried a hash table? You should be able to do this in a single pass of the linked list.
- Without extra space, you'll need O(N^2) time. Try using two pointers, where the second one searches ahead of the first one.
Solution
本题需要操作的是一个无序单链表，因此重复的元素不一定在相邻的位置上，如果要达到O(N)时间复杂度，可以用一个set存储遍历过的元素，若set内存在该元素，则删除。
public ListNode removeDups(ListNode head) {
ListNode preNode = null, curNode = head;
Set<Integer> valSet = new HashSet<>();
while (curNode != null) {
if (valSet.add(curNode.val)) {
preNode = curNode;
} else {
preNode.next = curNode.next;
}
curNode = curNode.next;
}
return head;
}
题目第二问要求空间复杂度为O(1)，那么只能通过两层循环。设置两个指针，外部循环遍历每个结点，内部循环从当前结点的下一个开始遍历，如果遇到重复则删除。
public ListNode removeDups(ListNode head) {
ListNode preNode = head, curNode = head;
while (preNode != null) {
curNode = preNode.next;
while (curNode != null) {
if (curNode.val == preNode.val) {
preNode.next = curNode.next;
}
curNode = curNode.next;
}
preNode = preNode.next;
}
return head;
}
