Posted on by Kalkicode
Code Single linked list

Remove duplicates from a sorted linked list

The problem at hand is to remove duplicate nodes from a sorted singly linked list. This entails eliminating nodes with duplicate values, such that the resulting linked list contains only unique values in ascending order.

Problem Description

Given a sorted singly linked list, we need to modify it in such a way that all duplicate elements are removed, and only distinct elements are retained. The relative order of the unique elements should be preserved.

Example

Consider the following sorted linked list:

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5 -> 6 -> 7

After removing duplicates, the modified linked list should be:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

Idea to Solve the Problem

Sorted Linked List After Remove duplicates nodes

To solve this problem, we can iterate through the linked list while maintaining two pointers - one pointing to the current node and another to the next node. If the current node's value is equal to the next node's value, we skip the next node by adjusting pointers. If they are not equal, we move both pointers ahead. This way, we can effectively remove duplicates while updating the linked list's structure.

Pseudocode

deleteDuplicates(linkedList):
    if linkedList.head is NULL:
        return
    
    current = linkedList.head
    
    while current is not NULL:
        nextNode = current.next
        while nextNode is not NULL and current.data = nextNode.data:
            nextNode = nextNode.next
        
        current.next = nextNode
        current = nextNode

Algorithm Explanation

  1. Start with the current pointer pointing to the head of the linked list.
  2. Traverse through the linked list using the current pointer: a. Initialize a nextNode pointer to the node next to the current node. b. Check if nextNode exists and has the same value as the current node. If yes, move the nextNode pointer to the next node with a different value. c. Update the current node's next pointer to point to the nextNode. d. Update the current pointer to the nextNode.
  3. Repeat step 2 until the current pointer reaches the end of the linked list.
  4. The linked list will now be free of duplicate nodes.

Code Solution

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. This is because we are iterating through each node once and removing duplicates in a linear manner.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment