Remove Duplicate Elements from a Sorted Linked List

Given a singly linked list sorted in ascending order, the task is to remove all duplicates such that each element appears only once.

Input-Output Examples

Example 1:

  • Input: 1 -> 1 -> 2 -> NULL
  • Output: 1 -> 2 -> NULL

Example 2:

  • Input: 1 -> 1 -> 2 -> 3 -> 3 -> NULL
  • Output: 1 -> 2 -> 3 -> NULL

Example 3:

  • Input: 1 -> 1 -> 1 -> NULL
  • Output: 1 -> NULL

Approach:

To remove duplicates from a sorted linked list, we can use a single pointer to traverse the list. We compare the current node's value with the next node's value. If they are the same, we skip the next node by adjusting the current node's next pointer. Otherwise, we move the pointer to the next node.

Steps to implement:

  1. Initialize a Pointer:
    • Use a pointer to traverse the list starting from the head.
  2. Traverse the List:
    • Compare the current node with the next node.
    • If they are the same, update the current node's next pointer to skip the duplicate node.
    • Otherwise, move the pointer to the next node.

C++ program to remove duplicate elements from a sorted Linked List

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Function to remove duplicates from a sorted linked list
ListNode* removeDuplicates(ListNode* head) {
    if (head == NULL) return head;

    ListNode* current = head;
    while (current != NULL && current->next != NULL) {
        if (current->val == current->next->val) {
            ListNode* temp = current->next;
            current->next = current->next->next;
            delete temp;
        } else {
            current = current->next;
        }
    }

    return head;
}

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating a sorted linked list: 1 -> 1 -> 2 -> 3 -> 3 -> NULL
    ListNode* head = new ListNode(1);
    head->next = new ListNode(1);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(3);

    // Remove duplicates from the sorted linked list
    head = removeDuplicates(head);
    cout << "After removing duplicates: ";
    printList(head);

    return 0;
}

Java program to remove duplicate elements from a sorted Linked List

java

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Main {
    // Function to remove duplicates from a sorted linked list
    public static ListNode removeDuplicates(ListNode head) {
        if (head == null) return head;
        
        ListNode current = head;
        while (current != null && current.next != null) {
            if (current.val == current.next.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        
        return head;
    }

    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating a sorted linked list: 1 -> 1 -> 2 -> 3 -> 3 -> NULL
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(3);

        // Remove duplicates from the sorted linked list
        head = removeDuplicates(head);
        System.out.print("After removing duplicates: ");
        printList(head);
    }
}

Python program to remove duplicate elements from a sorted Linked List

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Function to remove duplicates from a sorted linked list
def remove_duplicates(head):
    current = head
    while current and current.next:
        if current.val == current.next.val:
            current.next = current.next.next
        else:
            current = current.next
    return head

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating a sorted linked list: 1 -> 1 -> 2 -> 3 -> 3 -> NULL
head = ListNode(1)
head.next = ListNode(1)
head.next.next = ListNode(2)
head.next.next.next = ListNode(3)
head.next.next.next.next = ListNode(3)

# Remove duplicates from the sorted linked list
head = remove_duplicates(head)
print("After removing duplicates:", end=" ")
print_list(head)

DSA

4996

653

Related Articles