82 Remove Duplicates from Sorted List II

1. Question

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving onlydistinctnumbers from the original list.
For example, Given1->2->3->3->4->4->5, return1->2->5. Given1->1->1->2->3, return2->3.

2. Implementation

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode deleteDuplicates(ListNode head) {
11
ListNode dummy = new ListNode(0);
12
dummy.next = head;
13
14
ListNode preNode = dummy, curNode = head;
15
16
while (curNode != null) {
17
while (curNode.next != null && curNode.val == curNode.next.val) {
18
curNode = curNode.next;
19
}
20
21
if (preNode.next != curNode) {
22
preNode.next = curNode.next;
23
}
24
else {
25
preNode = preNode.next;
26
}
27
curNode = curNode.next;
28
}
29
return dummy.next;
30
}
31
}
Copied!

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(1)