Question

Formatted question description: https://leetcode.ca/all/82.html

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.

@tag-linkedlist

Algorithm

Here we need to delete all the duplicates. Because there may be duplicates at the beginning of the linked list, the head pointer will change if it is deleted, but the head pointer of the linked list needs to be returned in the end.

Therefore, you need to define a new node, then link the original linked list, and then define a precursor pointer and a current pointer. Each current pointer points to the newly created node. The current pointer starts from the next position and traverses down.

  • If the same is encountered, it will continue. Next, until a different item is encountered, the next of the predecessor pointer points to the different element below.
  • If the first element traversed by the current pointer is not the same, move the predecessor pointer down one place.

Code

Java

public class Remove_Duplicates_from_Sorted_List_II {

	public ListNode deleteDuplicates(ListNode head) {

		if (head == null) {
			return head;
		}

		ListNode dummy = new ListNode(0);
		dummy.next = head;

		ListNode prev = dummy;
		ListNode current = head;

		while (current != null) {

			boolean dup = false;

			// probe next to see if duplicate
			while (current.next != null && current.val == current.next.val) {
				current = current.next;
				dup = true;
			}

			if (dup) { // prev staying the same
				prev.next = current.next;
				current = current.next;
			} else {
				prev = current;
				current = current.next;
			}
		}

		return dummy.next;
	}

}

All Problems

All Solutions