### 题目

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.

### 和后一个比较，不使用额外空间

Remove Duplicates From Sorted List Two一样，直接跳到值相同的最后一个元素。然后直接修改指针。

#### 代码

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode sentinel = new ListNode(0), res = sentinel;
while (cur != null) {
while (cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
} // stop at last node holds the same value
res.next = cur;
res = res.next;
cur = cur.next;
}
res.next = null;
return sentinel.next;
}
}


### 和前一个比较，不用额外空间

#### 代码

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode sentinel = new ListNode(0), res = sentinel;
ListNode pre = null, cur = head;
while (cur != null) {
if (pre == null || cur.val != pre.val) {
res.next = cur;
res = res.next;
}
pre = cur; cur = cur.next;
}
res.next = null;
return sentinel.next;
}
}


### 用$O(1)$额外空间，记录上一个元素

#### 代码

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode sentinel = new ListNode(0), res = sentinel;
Integer register = null;
while (cur != null) {
if (register == null || cur.val != register) {
res.next = cur;
res = res.next;
register = cur.val;
}
cur = cur.next;
}
res.next = null;
return sentinel.next;
}
}


### 一段完美的代码

public ListNode deleteDuplicates(ListNode head) {
while (current != null && current.next != null) { // 和下一个元素比较
if (current.next.val == current.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}