Remove Duplicates from Sorted List II

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.

Example1

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

SOLVING

We’ll use Two Pointers method to solve this problem

Steps

  1. Create a Node dummy with val (0 for this example) pointing to head
  2. Create a Node prev equal to dummy
  3. Parcor the Linked List:
    • If the current value and the next are the same:
      • Loop until the node value is different
      • prev->next equal to this node
    • Otherwise move prev and head of a node
  4. Return the next of dummy (previously the pointer to head)

Code

class Solution {
public:
  ListNode *deleteDuplicates(ListNode *head) {
    ListNode *dummy = new ListNode(0, head);
    ListNode *prev = dummy;

    while (head) {
      if (head->next && head->val == head->next->val) {
	while (head->next && head->val == head->next->val)
	  head = head->next;
	prev->next = head->next;
      } else
	prev = prev->next;
      head = head->next;
    }
    return dummy->next;
  }
};