Monday, August 11, 2014

Leetcode: 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.


Understand the problem:
The problem asks for removing duplicated numbers from a linked list. Note the the difference from the last post is all duplicated numbers are deleted.  For example,
1  ->  1  -> 1  -> 2  , return 2

For an empty linked list, return null
For a linked list with only 1 element, return the original linked list. 

Solution:
We still use two pointers, p and q. q pointer is one step ahead of p at beginning. Move q pointer if q is duplicated. If q pointer moves more than one steps (has duplicates), move p.next = q.next. Else, move p and q one step ahead. The crux is to determine if q moves multiple steps. If yes, it means q pointer has duplicates, we should jump the q pointer. Else, q pointer should be saved. For example,
0 -> 1  -> 2 ->3, where p and q points to 0 and 1, respectively. Since 1 has no duplicates afterwards, we move both p and q one step ahead.
0  -> 1  -> 1 -> 2  -> 3, where again p and q points to 0 and 1, respectively. Since now i has duplicates afterwards, we should jump the 1s and points p to the value of 2.

Code (Java):
/**
 * 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;
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        head = helper;
        
        ListNode p = head;
        ListNode q = head.next;
        
        while (q != null) {
            while (q.next != null && q.val == q.next.val) {
                q = q.next;
            }
            if (p.next != q) {
                p.next = q.next;
                if (q != null) q = q.next;
            } else {
                p = p.next;
                q = q.next;
            }
        }
        return head.next;
    }
}

Discussion:
Note that we used a helper node ahead of the head node. This is to avoid the complexities in deleting the head node, which may be the case for this question.  Using helper node is a common usage when updating the head node.

Updates on 10/7/14:
/**
 * 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;
        }
        
        ListNode dummyNode = new ListNode(Integer.MIN_VALUE);
        dummyNode.next = head;
        
        ListNode prev = dummyNode;
        ListNode curr = head;
        
        while (curr != null && curr.next != null) {
            ListNode next = curr.next;
            if (curr.val == next.val) {
                while (curr.next != null && curr.val == next.val) {
                    curr = curr.next;
                    next = next.next;
                }
            
                prev.next = next;
                curr = next;
            } else {
                prev = prev.next;
                curr = curr.next;
            }
        }
        
        return dummyNode.next;
    }
}


No comments:

Post a Comment