Remove Dups: 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?
解答1
用一个Set来记录哪些data出现过，用两个指针一前一后来遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public void removeDups(Node head) {
Set<Object> datum = new HashSet<>();
Node p1 = null;
Node p2 = head;
while(p2 != null) {
if (datum.contains(p2.data)) {
p1.next = p2.next;
} else {
datum.add(p2.data);
p1 = p2;
}
p2 = p2.next;
}
}
|
时间复杂度：O(n)
空间复杂度：O(n)
解答2
如果不用Set，直接想到的办法是p1指向在第一个节点，p2则从下一个节点开始跑，如果发现重复，则删除p2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public void removeDups(Node head) {
Node p1 = head;
while(p1 != null && p1.next != null) {
Node p2 = p1;
while(p2.next != null) {
if (p1.data == p2.next.data) {
// 删除p2.next
p2.next = p2.next.next;
continue;
}
p2 = p2.next;
}
p1 = p1.next;
}
}
|
时间复杂度：O(n^2)
空间复杂度：O(1)，因为是in place
评论