Remove Duplicates from Sorted List

---

Remove Duplicates from Sorted List: Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1:

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

---

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,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.

---

Try this Problem on your own or check similar problems:

1. Remove Linked List Elements
2. Remove Duplicates from Sorted List II

Solution:

Java

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;

    ListNode dummy = new ListNode(-1, head), curr = dummy.next;

    while(curr != null){
        while(curr.next != null && curr.val == curr.next.val){
            curr.next = curr.next.next;
        }
        curr = curr.next;
    }

    return dummy.next;
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
  if (head === null) return null;

  let dummy = new ListNode(-1, head);
  let curr = dummy.next;

  while (curr !== null) {
    while (curr.next !== null && curr.val === curr.next.val) {
      curr.next = curr.next.next;
    }
    curr = curr.next;
  }

  return dummy.next;
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None

        dummy = ListNode(-1, head)
        curr = dummy.next

        while curr:
            while curr.next and curr.val == curr.next.val:
                curr.next = curr.next.next
            curr = curr.next

        return dummy.next

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) return nullptr;

        ListNode* dummy = new ListNode(-1, head);
        ListNode* curr = dummy->next;

        while (curr != nullptr) {
            while (curr->next != nullptr && curr->val == curr->next->val) {
                ListNode* temp = curr->next;
                curr->next = temp->next;
                delete temp;
            }
            curr = curr->next;
        }

        return dummy->next;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

The problem is really similar to the Remove Linked List Elements where we have a sentinel node and we iterate through list and for each node check if it's next node has the same value, if it has we relink the current node to point to the next node and repeat the process until we find a node with a value that's different than the value at current node. Dummy node will be pointing to the new head so we just have to return dummy.next.