Problem

Given a sorted linked list, delete all duplicates such that each element appear only once.

Examples

Example 1:

Given 1->1->2, return 1->2.

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

Example 2:

Given 1->1->2->3->3, return 1->2->3.

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

Similar problem - Remove duplicates from Sorted List 2.

Solution

The key of this problem is using the right loop condition. And change what is necessary in each loop.

Also, we don’t need to use any dummy node in linked list here, as even though the duplicates start at head, we still have another node, which we can take care of.

Method 1 - Iterative Solution

Dry Run

Here is the video explanation:

Code

Java
public ListNode deleteDuplicates(ListNode head) {
	if (head == null || head.next == null) {
		return head;
	}
	ListNode curr = head;
	while (curr.next != null) {
		if (curr.val == curr.next.val) {
			curr.next = curr.next.next;
		}
		else {
			curr = curr.next;
		}
	}
	return head;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)