# Remove Duplicates from Sorted List

• Do we need to delete the allocated memory for the duplicated nodes?

• @c.tianyi1989 if you're using C/C++, you would need to free the memory manually.

• You can use Java. Put all elements in a LinkedHashSet (maintains order even in a set). Then put all of these elements from the Set into a different linked list and return it.

• @1337c0d3r That depends on the way the memory allocated.

• @1337c0d3r, Do you mean we have to delete the space of the "duplicate" elements?

• @dirty_ninja, Manually 'free'ing up memory is only applicable in C/C++. It is not required in Java or Python.

• There are two methods to solve this problem, recursive one and non-recursive one. The method in your article is recursive, which is O(1) space and O(n) time. The non-recursive one which is not given is O(n) space and O(n) time.

• ``````struct ListNode* deleteDuplicates(struct ListNode* head) {
return NULL;

struct ListNode* p = NULL, *q = NULL;

q = p->next;

while(q)
{
struct ListNode *tmp = q->next;

if (!(p->val ^ q->val))
{
//same element
p->next = tmp;
free(q);
q = tmp;
}
else
{
p = q;
q = q->next;
}
}

}
``````

• This solution would solve if the duplicates are next to each other. What if I have linked list that looks like 1->2->3->1->4?

• @kkamaraj it's sorted list.

• @EnzoHarris you are right! Thanks for the clarification.

• this is the simplest approch i have seen.

• @coolseraz what's the time complexity of that approach?

• I diot ! I have ignored the 'sorted'!

• Simple and beautiful !

• Is it necessary to return head at the end??

• @alex1461 I think it's necessary as head always returs you the first node of your linkedlist.

• Do we need the else statement at all?

• yes, we need else statement otherwise it won't work in case of duplicate values occur more than two times.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.