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)

0 thoughts on “5) Remove Duplicates from Sorted List II”

  1. Pingback: 13) Remove Nth Node From End of List – Developers Inspired

Leave a Comment

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