Remove Duplicates from Linked List – Java Program

This Java program demonstrates how to remove duplicate elements from a linked list. The program includes the implementation of the linked list nodes and the logic to remove duplicates.

Program Structure

The program is structured into three main components:

1. ListNode Class: Defines the node structure for the linked list.
2. RemoveDuplicates Class: Contains the method to remove duplicate elements from the linked list.
3. Main Class: Contains the main method to execute the program and test the removal functionality.

Java Code

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public class RemoveDuplicates {
        /**
         * Removes duplicate elements from a linked list.
         * 
         * @param head The head of the linked list.
         * @return The head of the linked list with duplicates removed.
         */
        public ListNode removeDuplicates(ListNode head) {
            // Use a set to track seen values
            Set seen = new HashSet<>();
            ListNode current = head;
            ListNode previous = null;
            
            while (current != null) {
                if (seen.contains(current.val)) {
                    // Remove the duplicate
                    previous.next = current.next;
                } else {
                    // Add the value to the set and move previous pointer
                    seen.add(current.val);
                    previous = current;
                }
                current = current.next;
            }
            
            return head;
        }
    }

    public class Main {
        public static void main(String[] args) {
            // Create a linked list with duplicates for testing
            ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(2, new ListNode(4, new ListNode(3))))));
            
            // Remove duplicates
            RemoveDuplicates remover = new RemoveDuplicates();
            ListNode cleanedList = remover.removeDuplicates(head);
            
            // Print the cleaned list
            System.out.println("Linked List after removing duplicates:");
            printList(cleanedList);
        }
        
        // Helper method to print the linked list
        private static void printList(ListNode head) {
            ListNode current = head;
            while (current != null) {
                System.out.print(current.val + " ");
                current = current.next;
            }
            System.out.println();
        }
    }
    

Explanation

ListNode Class: This class represents a node in the linked list. Each node contains an integer value and a reference to the next node.

RemoveDuplicates Class: This class contains the method removeDuplicates that removes duplicate elements from the linked list. It uses a set to track seen values and efficiently removes duplicates.

Main Class: This class is used for testing the removal functionality. It creates a sample linked list with duplicates, removes the duplicates using the RemoveDuplicates class, and prints the cleaned list.