1. Introduction

Linked lists are a fundamental data structure in computer science. When dealing with sorted linked lists, it’s common to encounter scenarios where the list might contain duplicate elements. In this blog post, we’ll explore a Java program that removes these duplicates from a sorted linked list.

2. Program Steps

1. Initialize three pointers: current, next_next, and next.

2. current will traverse the list.

3. Compare the data of the current node and the next node.

4. If they are equal, update the next pointer of the current node to the node after next using next_next.

5. If they aren’t equal, move the current pointer to the next node.

6. Repeat these steps until current or next reaches the end of the list.

3. Code Program

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class LinkedList {
    Node head;

    // Function to remove duplicates from a sorted list
    void removeDuplicates() {
        Node current = head;

        while (current != null) {
            Node next = current.next;

            // Compare current node with the next node
            if (next != null && current.data == next.data) {
                Node next_next = next.next;
                current.next = next_next; // Remove the next node
            } else {
                current = next; // Move to next node
            }
        }
    }

    // Function to print the linked list
    void printList() {
        Node n = head;
        while (n != null) {
            System.out.print(n.data + " ");
            n = n.next;
        }
    }

    // Function to insert a new Node at the last
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.append(1);
        list.append(2);
        list.append(2);
        list.append(3);
        list.append(4);
        list.append(4);
        list.append(5);

        System.out.println("Original Linked list with duplicates:");
        list.printList();

        list.removeDuplicates();

        System.out.println("\nLinked list after removing duplicates:");
        list.printList();
    }
}

Output:

Original Linked list with duplicates:
1 2 2 3 4 4 5
Linked list after removing duplicates:
1 2 3 4 5

4. Step By Step Explanation

1. We define a basic Node class to create nodes for our linked list.

2. The LinkedList class provides various methods, including removeDuplicates, which will remove the duplicate elements from our sorted linked list.

3. The removeDuplicates method works by iterating over the linked list using the current pointer.

4. For each node, it compares the data of current and the data of the next node.

5. If the data is identical (indicating a duplicate), the next node is skipped by pointing current.next to next_next.

6. If the data isn't identical, the traversal moves on to the next node.

7. The main method demonstrates the functionality by:

a. Creating a sorted linked list with duplicates.

b. Printing the original list.

c. Removing duplicates using removeDuplicates.

d. Printing the modified list.

By using this method, we efficiently remove duplicates from a sorted linked list. Remember that this method assumes that the list is already sorted.