83 Remove Duplicates from Sorted List

1. Question

Given a sorted linked list, delete all duplicates such that each element appear onlyonce.
For example, Given1->1->2, return1->2. Given1->1->2->3->3, return1->2->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
if (head == null) {
12
return head;
13
}
14
15
ListNode preNode = head, curNode = head.next;
16
while (curNode != null) {
17
if (preNode.val == curNode.val) {
18
preNode.next = curNode.next;
19
}
20
else {
21
preNode = preNode.next;
22
}
23
curNode = curNode.next;
24
}
25
return head;
26
}
27
}
Copied!

3. Time & Space Complexity

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