82. Remove Duplicates from Sorted List II.md

82. Remove Duplicates from Sorted List II

---

leetcode Daily Challenge on January 5th, 2021.

leetcode-cn Daily Challenge on March 25th, 2021.

---

Difficulty : Medium

Related Topics : LinkedList

---

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

---

Solution

• mine
  • Java

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 38.8 MB, less than 6.98% of Java online submissions

      public ListNode deleteDuplicates(ListNode head) {
          if(head == null || head.next == null){
              return head;
          }
          ListNode[] res = check(head);
          if(res[1] != null && head.val == res[1].val){
              head = res[0];
          }
          return head;
      }
      
      public ListNode[] check(ListNode node) {
          ListNode[] temp = new ListNode[2];
          if(node == null || node.next == null){
              temp[0] = node;
              temp[1] = null;
          }else{
              ListNode[] res = check(node.next);
              if(res[1] != null && node.val == res[1].val ){
                  return res;
              }
              if(res[0] == null){
                  node.next = res[0];
                  res[0] = node;
                  return res;
              }
              if(node.val == res[0].val){
                  node = res[0].next;
                  temp[1] = new ListNode(res[0].val);
              }else{
                  node.next = res[0];
              }
              temp[0] = node;
          }
          return temp;
      }
      

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 39 MB, less than 13.57% of Java online submissions

      // O(N)time
      // O(1)space
      public ListNode deleteDuplicates(ListNode head) {
          ListNode temp = new ListNode(-101, head);
          ListNode cur = head;
          ListNode pre = temp;
          int preVal = temp.val;
          while(cur != null){
              if(cur.val == preVal ||  cur.next != null && cur.val == cur.next.val){
                  preVal = cur.val;    
              }else{
                  preVal = cur.val;
                  pre.next = cur;
                  pre = pre.next;
              }
              cur = cur.next;
          }
          pre.next = cur;
          return temp.next;
      }
      

---

• the most votes
  • Runtime: 0 ms, faster than 100.00%, Memory Usage: 38.9 MB, less than 6.98% of Java online submissions

    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) return null;
        ListNode FakeHead=new ListNode(0);
        FakeHead.next=head;
        ListNode pre=FakeHead;
        ListNode cur=head;
        while(cur!=null){
            while(cur.next!=null&&cur.val==cur.next.val){
                cur=cur.next;
            }
            if(pre.next==cur){
                pre=pre.next;
            }
            else{
                pre.next=cur.next;
            }
            cur=cur.next;
        }
        return FakeHead.next;
    }
    

---