5) 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 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) 
    {
        ListNode cur = head;
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        int prev = 999;
        while(cur != null && cur.next != null)
        {
            if(prev == cur.val || cur.val == cur.next.val)
            {
                prev = cur.val;
                cur = cur.next;
            }
            else
            {
                ListNode newNode = new ListNode(cur.val);
                temp.next = newNode;
                cur = cur.next;
                temp = temp.next;
            }
        }
        if(cur != null && prev != cur.val)
        {
            temp.next = cur;
        }
        return dummy.next;
    }
}

Time Complexity: O(n)

Space Complexity: O(n)

One thought on “5) Remove Duplicates from Sorted List II

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s