Remove Duplicates from Sorted List I & II, Remove Duplicates from Sorted Array I & II

Remove Duplicates from Sorted List I

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.

Solution

Two loops One pointer solution, only move cursor to next when we confirmed cur.next.val!==cur.val.

public ListNode deleteDuplicates(ListNode head) {
    ListNode h = head;
    if(head==null||head.next==null) return head;
    ListNode cur= head;
    while(cur!=null){
        while(cur.next!=null&&cur.next.val==cur.val)
        cur.next=cur.next.next;
        cur=cur.next;
    }
    return h;
}

Or we can use only one loop:

public ListNode deleteDuplicates(ListNode head) {
      ListNode h = head;
      if(head==null||head.next==null) return head;
      ListNode cur= head;
      while(cur!=null){
          ListNode tmp=cur.next;
          if(tmp!=null&&tmp.val==cur.val){
              cur.next=tmp.next;}
          else cur=cur.next;
      }
      return h;
  }

---

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution

Similar to how we deleted duplicates in I, now we add a pre pointer to record the last non-duplicate element, and a dummy head to deal with cases where head needs to be removed. Note: we can only move pre to next when we confirmed now cur is pointing to a unique element.

public ListNode deleteDuplicates(ListNode head) {
       ListNode dummy=new ListNode(0);
       dummy.next=head;
       ListNode cur=head, pre=dummy;
       while(cur!=null&& cur.next!=null){
           //if dup found, keep cur at last dup element
           if(cur.val==cur.next.val){
           while(cur.next!=null&&cur.val==cur.next.val){cur=cur.next;}
           //remove the dups, remember to move the cur for detecting more dups
           pre.next=cur.next;
           cur=cur.next;}
           //move the two pointers next when no dup found
           else {pre=pre.next; cur=cur.next;}     
       }       
       return dummy.next;
   }

---

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

Solution

Just replace current element with the first non-duplicate, in other words, non-equal-to-current element.

public int removeDuplicates(int[] A) {
          int n=A.length;
          int count=0;
          if(A.length==0) return 0;
          for(int i=0;i<n;i++){
              //count points to the last element of our new array, i pointer finds the next non-dup element
              if(A[i]!=A[count]){A[++count]=A[i];}
          }return count+1;
      }

---

Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].

Solution

The solution is a bit tricky. We use two pointers, pre to keep the second duplicate element, and cur to keep the first element different from current duplicate element. Then we replcace the next element of pre, to whatever next element cur is pointing at.

public int removeDuplicates(int[] A) {
       int n = A.length;
       int pre=1,cur=2;
       if(n==0||n==1||n==2) return n;
       while(cur<n){
           //confirm no three dups in new array  
           if(A[cur]==A[pre-1]){
               //cur points to the first element different from current dups
               cur++;
           }
           else {
               //move pre to the third dup element
               pre++;
               //replace the third dup with the next element 
               A[pre]=A[cur];
               cur++;
           }
       }
       return pre+1;
       
   }