(Remove Duplicates from Sorted List)

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Thoughts:
This question is the same as ‘remove duplicates from sorted array’ except that we need to deal with linked list this time. The algorithm is the same.

Code (Java):

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null)
            return null;
        ListNode j = head;
        ListNode i = head.next;
        while(i != null) {
            if(j.val != i.val) {
                j = j.next;
                j.val = i.val;
            }
            i = i.next;
        }
        j.next = null;
        return head;
    }
}

Code (C++):

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL)
            return head;
        ListNode *j = head;
        ListNode *i = j -> next;
        while(i != NULL) {
            if(i -> val != j -> val) {
                j = j -> next;
                j -> val = i -> val;
            }
            i = i -> next;
        }
        j -> next = NULL;
        return head;
    }
};
Advertisements

3 Comments (+add yours?)

  1. dtaspinar
    Aug 29, 2012 @ 11:59:56

    Reblogged this on CompSci log.

    Reply

  2. Lakshmi Narasimhan Ramakrishnan
    Jan 01, 2014 @ 23:32:50

    In c++ unless you use shared pointers you need to delete the duplicate nodes explicitly to prevent memory leaks

    Reply

  3. frank
    Jan 19, 2014 @ 14:58:03

    Hi, how would you implement this recursively in java?

    Reply

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

%d bloggers like this: