Problem

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.

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Kind of follow up of Remove duplicates from Sorted List 1.

Solution

Method 1 - Iterative

We can use 2 pointers - curr and curr.next to process the list, similar to Remove duplicates from Sorted List 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public ListNode deleteDuplicates(ListNode head) {
	ListNode dummy = new ListNode(0);
	dummy.next = head;

	ListNode curr = dummy;
	while (curr.next != null && curr.next.next != null) {
		if (curr.next.val == curr.next.next.val) {
			int dup = curr.next.val;
			while (curr.next != null && curr.next.val == dup) {
				curr.next = curr.next.next;
			}
		} else {
			curr = curr.next;
		}

	}

	return dummy.next;
}

Complexity

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

Method 2 - Recursive

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

Complexity

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