Leetcode–Remove Duplicates from Sorted List II

The 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.

Notes:

  1. The head node could be deleted, use a common trick of fake head.
  2. Keep three nodes: prepre, pre, and current. If pre and current have same value, then link prepre.next to curent.next
  3. Mistake I made: Since pre can be deleted already in last iteration, prepre should not get updated when pre is deleted. Also note that pre should not get updated when deleted, may have more than one same node as pre, so need to continue the check.

Java Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next==null)
            return head;
        // create a fake head
        ListNode fkHead = new ListNode(0);
        fkHead.next = head;
        ListNode prepre = fkHead;
        // pre and current are set to same node, current will advance at the beginning of each iteration.
        ListNode pre = head;
        ListNode current = head;
        boolean preDel = false;
        while(current.next!=null){
            current = current.next;
            if(current.val==pre.val){
                prepre.next = current.next;
                current = prepre;
                preDel = true;
                //no need to update pre here
            }
            else{
                //--!!!-- pre could already be deleted, in that case prepre stay
                pre = current;
                if(!preDel)
                   prepre = prepre.next;
                preDel = false;
            }
        }
        return fkHead.next;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s