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.
Method:
We keep a pointer to previous node, if current node's val is different, then append current node. If not, then set next node to be nil.
Solution:
Time: O(n)
Space: O(1)
/**
* Definition for singly-linked list.
* class ListNode {
* public int val;
* public ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
public class Solution {
public ListNode deleteDuplicates(ListNode A) {
if (A == null || A.next == null) return A;
ListNode head = A;
ListNode prev = A;
ListNode curr = A.next;
while (curr != null) {
ListNode next = curr.next;
if (curr.val != prev.val) {
prev.next = curr;
prev = curr;
curr.next = null;
} else {
prev.next = null;
}
curr = next;
}
return head;
}
}