[LeetCode] 82. 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.

Thought process:

It's not clear that we can return head as the result because head might need to be deleted. We can solve this by inserting a dummy node before head. After deleting duplicate nodes, we can return dummy->next.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode current = dummy; while (current.next != null && current.next.next != null) { if (current.next.val == current.next.next.val) { int duplicate = current.next.val; while (current.next != null && current.next.val == duplicate) { current.next = current.next.next; } } else { current = current.next; } } return dummy.next; } }

Time complexity:
O(n). Although there are two nested while loops, they are both making progress on the same list.