Remove duplicates from a sorted Doubly Linked List

Easy
0/40
profile
Contributed by
259 upvotes
Asked in companies
AdobeAppleAmazon

Problem statement

A doubly-linked list is a data structure that consists of sequentially linked nodes, and the nodes have reference to both the previous and the next nodes in the sequence of nodes.


You are given a sorted doubly linked list of size 'n'.


Remove all the duplicate nodes present in the linked list.


Example : 
Input: Linked List: 1 <-> 2 <-> 2 <-> 2 <-> 3

Output: Modified Linked List: 1 <-> 2 <-> 3

Explanation: We will delete the duplicate values ‘2’ present in the linked list.


Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'n', the number of elements in the linked list.
The second line contains 'n' integers, the elements of the linked list separated by a single space.


Output Format : 
Print a single line, the final linked list.


Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Sample Input 1 :
5
1 2 2 2 3


Sample Output 1 :
1 2 3


Explanation For Sample Input 1 :
We will delete the duplicate values ‘2’ present in the linked list.


Sample Input 2 :
4
1 2 3 4


Sample Output 2 :
1 2 3 4


Explanation For Sample Input 2 :
The list contains no duplicates, so the final list is unchanged.


Expected time complexity :
The expected time complexity is O('n').


Constraints :
1 <= 'n' <= 10^5
1 <= 'data' in any node <= 10^6

Time limit: 1 sec
Hint

If the next element is the same as the current one, try adjusting the links to remove the next element!

Approaches (1)
Brute Force

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’.
Time Complexity

O(n), where ‘n’ is the length of the linked list.

Each element in the input list is traversed exactly once, and the links are adjusted accordingly to remove duplicates.

Hence the time complexity is O(n).

Space Complexity

O(1)

No extra space is used except ‘cur’.

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Remove duplicates from a sorted Doubly Linked List
Full screen
Console