# LeetCode — Remove Duplicates from Sorted List II

Problem Link: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

Problem Description: Given the `head`

of a sorted linked list, *delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list*. Return *the linked list **sorted** as well*.

Approach Used: Linked-list, Iteration

Explanation: This question is a slight modification of a standard linked list question in which we have to keep a single element of each value and delete all the duplicates. In this question since we might have to delete the current node also if there are multiple nodes with the same value, we should at each point keep track of the previous node. Then we can simple readjust links to make the previous node (last node before the chain of duplicate nodes) point to the node after all the duplicate nodes. We’ll have to handle one more scenario when the first node itself has multiple duplicates. In this case, we will have to make the head point to the first node in the list which does not have duplicates. To check if the first node itself has duplicates we can simply see if the previous node is null or not. Because in the entire list only head node will have its previous node as null.

Code: (Java)

`public ListNode deleteDuplicates(ListNode head) {`

//base case - empty list or single node (there can be no duplicates)

if(head==null || head.next==null)

return head;

//storing head in another node so that original list is not lost

ListNode temp = head;

//for storing previous node at each point

ListNode prev = null;

//since we will be comparing value of adjacent nodes we should ensure that both are not null

while(temp!=null && temp.next!=null){

//if duplicate found

if(temp.val==temp.next.val){

//move forward until non duplicate element found

while(temp!=null && temp.next!=null && temp.val==temp.next.val)

temp = temp.next;

//if previous is not null means we are not at head

//so previous should point to next node after chain of duplicates

if(prev!=null)

prev.next = temp.next;

//else head needs to point to first non duplicate

else

head = temp.next;

}

//else make previous equal to current node to move ahead with traversal

else

prev = temp;

//increment current node for next set of nodes

temp = temp.next;

}

//return head node of updated list

return head;

}

Complexity:

Space complexity: O(1). Since we are only readjusting links and not even using recursion, no new memory allocation is required.

Time complexity: O(n). Since we will be visiting each node exactly once.

Here n is the number of nodes in the original linked list.