Remove Duplicates From Sorted List

Posted: 21 Sep, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You want to play with your friend, but your friend has pending homework, help him complete that.

You are given a ‘Head’ of a sorted linked list. You can remove some values from the linked list. In the end, you must return a sorted linked list that contains no adjacent values that are equal.

For Example :
If the given linked list is: 1 -> 2 -> 2 -> 3

Then we will delete the duplicate value ‘2’ present in the linked list, and finally return the following list:
1 -> 2 -> 3
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first and only line of each test case contains the elements of the first linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
Output Format :
For each test case, print the final linked list. The elements of the linked list must be separated by a single space and terminated by -1.

Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 10      
0 ≤ Length ≤ 10^5
1 ≤ data ≤ 10^6 and data != -1

Time limit: 1 sec
Approach 1

Check if the current element has the same value as the next element, if so adjust the pointers such that the next to next element of the current element is the next element. Refer to the steps below for a better understanding.

 

The steps are as follows :

  • Initialize “cur” equal to ‘head’.
  • Run a while loop till cur and cur->next both are not NULL.
  • Check if the current element is equal to the next element, if so then set cur->next equal to cur->next->next so that the next to next element now becomes the next element ( ultimately removing one of the duplicates). 
  • If the current element is different from the next element, then set the “cur” pointer to point to the next element.
  • Finally, return ‘head’.
Try Problem