Remove Duplicates from Sorted List II

Problem

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.

Solution

Concise recursive solution

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        if (head.val == head.next.val) {
            while (head.next != null && head.val == head.next.val) head = head.next; //pass all duplicated nodes 
            return deleteDuplicates(head.next); 
        }
        else head.next = deleteDuplicates(head.next);
        return head;
    }
}

Two pointers iterative solution

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy, cur = head;
        while (cur != null) {
            while (cur.next != null && cur.val == cur.next.val) cur = cur.next;
            if (pre.next == cur) pre = pre.next;
            else pre.next = cur.next;
            cur = cur.next;
        }
        return dummy.next;
    }
}

Analysis

The difference between this problem and Remove Duplicates from Sorted List is that we need to completely delete all nodes appearing more than once
In the iterative solution, we have two pointers pre and cur
cur will be assigned to the next if there is duplicates
Then we use pre and pre.next to change the connection inside given linked list
At the end, we return dummy.next since it is the original head

In recursive solution, we use similar idea from iterative solution
If we find the duplicated, we move the current node until it's unique using while loop
After the loop, we need to check remaining nodes in the linked list, hence we do deleteDuplicates(head.next)
If we don't find any duplicates, we simply assign head.next by calling the function recursively
At the end, we need to return head as required
It is more concise than iterative solution but looks pretty vague as well
Like people say,

A programmer has to put the thought of recursion deep inside his/her mind.