2014
11-18

# LeetCode-Remove Duplicates from Sorted List[链表]

### Remove Duplicates from Sorted List

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.

// LeetCode, Remove Duplicates from Sorted List
// 递归版，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:

return dummy.next;
}
private:
static void recur(ListNode *prev, ListNode *cur) {
if (cur == nullptr) return;

if (prev->val == cur->val) { // 删除head
prev->next = cur->next;
delete cur;
recur(prev, prev->next);
} else {
recur(prev->next, cur->next);
}
}
};


// LeetCode, Remove Duplicates from Sorted List
// 迭代版，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
if (head == nullptr) return nullptr;

for (ListNode *prev = head, *cur = head->next; cur; cur = cur->next) {
if (prev->val == cur->val) {
prev->next = cur->next;
delete cur;
} else {
prev = cur;
}
}
}
};


Java代码:

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
while(current != null){
if(pre.val == current.val){
pre.next = current.next;
}else{
pre = pre.next;
}
current = current.next;
}
}