Remove duplicate nodes from sorted singly linked list in java(example/ algorithm)

• Given a sorted singly linked list containing duplicate elements.
• Remove duplicate elements or nodes from a single linked list.
  • Traverse the sorted singly linked list using iterative (non recursive) algorithm.

In a sorted linked list, all the duplicate elements must be lying adjacent to each others e.g. duplicates of 2 and 3 are lying together as shown in Fig 1.

Algorithm: remove duplicate elements/ nodes from a single linked list

• Start the iterating linked list from head
• Compare head element 1 with next element 2
  • Check 1 == 2 ? They are not equals.
  • Let move ahead in linked list
• Compare element 2 [Second node] with element 2 [Third node]
  • Check 2 == 2?  Yes, these are duplication nodes.
  • Let us remove the element 2 [Third node] from linked list
  • Save the reference of element 3 (fourth node)
    • nextNode = head.next.next
  • Delete element 2 at Third position
    • head.next = null
  • Now connect element 2 [Second position] with element 3 (fourth position)
    • head.next = nextNode
• We have removed element 2 [Earlier Third node] from linked list
• Now go ahead with iteration to remove rest of duplicate elements
  • We will remove duplicated element 3 from linked list in similar way
• We have shown the removal of duplicate elements in Fig 2.

Time complexity of algorithm is O(n).

Once we are done, with the removal of duplicate elements from linked list, our resultant linked list will be reduced to Fig 3. The linked list does not contain any duplicate elements.

Program – remove/delete duplicate nodes from sorted singly linked list in java.

1.) RemoveDuplicates Class:

The RemoveDuplicates class has following methods:

• insert function is used to prepare single linked list. (as shown in Fig 1)
• print method is used to print the single linked list.
• removeDuplicates method, removes the duplicates from single linked list

package org.learn.Question;

import org.learn.List.Node;

public class RemoveDuplicates {

	public static void removeDuplicates(Node head) {
		// first node to be inserted
		if (null == head) {
			System.out.println("Linked list is empty");
			return;
		}
		Node nextNode = null;
		while (head.next != null) {
			// check for duplicates
			// E.g 1->2->2->3
			if (head.data == head.next.data) {
				nextNode = head.next.next;
				// deleting next node...
				// let gc take care of it
				head.next = null;
				head.next = nextNode;
			} else {
				// no duplicate..move to next node
				head = head.next;
			}
		}
	}

	public static void insert(Node head, int data) {
		while (head.next != null)
			head = head.next;
		head.next = new Node(data);
	}

	public static void print(Node head) {
		while (head != null) {
			System.out.printf("%d ", head.data);
			head = head.next;
		}
		System.out.println("");
	}
}

2.) App Class:

We are performing following method in App class.

• We are creating the single linked list [Shown in Fig 1].
• RemoveDuplicates.removeDuplicates method is used to removed duplicates from single linked list.
• We are printing the linked list, after removing the duplicates elements.

package org.learn.Client;

import org.learn.List.Node;
import org.learn.Question.RemoveDuplicates;

public class App {
	public static void main(String[] args) {
		int[] listData = { 1, 2, 2, 3, 3, 9 };
		Node head = new Node(listData[0]);
		for (int count = 1; count < listData.length; count++)
			RemoveDuplicates.insert(head, listData[count]);

		System.out.printf("Linked list is : ");
		RemoveDuplicates.print(head);

		RemoveDuplicates.removeDuplicates(head);
		System.out.printf("Linked list after removing duplicates : ");
		RemoveDuplicates.print(head);
	}
}

3.) Node Class:

• Node class representing the node(s) of a single linked list

package org.learn.List;

public class Node {
	public int data;
	public Node next;

	public Node(int num) {
		this.data = num;
		this.next = null;
	}
}

Output – remove or delete duplicate nodes from sorted singly linked list in java

Linked list is : 1 2 2 3 3 9
Linked list after removing duplicates : 1 2 3 9

Download Code – remove delete duplicate nodes sorted linked list java