title: Remove Duplicates From Sorted List
tags:
- remove-duplicates-from-sorted-list
- No.83
- simple
- list
Description
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2
Output: 1->2
Example 2:
Input: 1->1->2->3->3
Output: 1->2->3
Corner Cases
- empty list
Solutions
Naive
Here we propose a new method to process list, that is adding a new Head before the original list.
0.
[old head] -> [x] -> [x] -> [x]
1.
[new head] -> [old head] -> [x]
This will make it more convenient for a pointer to traverse and compare.
Since the list is sorted, we only record the maxmium. The running time is O(n).
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
int m = -2147483648;
ListNode a = new ListNode(0);
a.next = head;
ListNode p = a;
while (p.next != null) {
if (m >= p.next.val) {
p.next = p.next.next;
}
else {
m = p.next.val;
p = p.next;
}
}
return a.next;
}
}
