Last Updated: 21 Sep, 2021

Remove duplicates from a sorted Doubly Linked List

Easy

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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

Solve now