Remove Duplicates from Sorted List I && II

Remove Duplicates from Sorted List I

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

public static ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode runner = head;
    while (runner.next != null) {
        if (runner.next.val == runner.val) {
            runner.next = runner.next.next;
        } else {
            runner = runner.next;
        }
    }
    return head;
}

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.

Example

Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

    public static ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }   
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode runner = dummyHead;
        int preValue = dummyHead.val;
        while(runner.next!=null){
            if(runner.next.val==preValue || 
            (runner.next.next!=null && runner.next.next.val == runner.next.val)){
                preValue = runner.next.val;//keep track of the previous value
                runner.next = runner.next.next;//delete runner.next
            }else{
                preValue = runner.next.val;
                runner = runner.next;//keep moving forward
            }
        }
        return dummyHead.next;
    }
FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *