How to remove duplicates from a sorted linked list ?

  • To write a removeDuplicates() function which takes a list sorted from the list any duplicate nodes to be deleted. The list should be traversed only once.

Algorithm

  • Traverse the head (or start) node from the list. Compare each node with its next node while traversing.
  • If same as the current node and data of next node to be delete that node. Before we delete a node, we need to store next pointer of the node.

Implementation

  • Functions other than removeDuplicates() are just to create a linked.
  • Linked list to be tested and removeDuplicates() from the list.
 Remove Duplicate From a Sorting Linked List

Sample Code in Java

class LinkedListExample 
{ 
	Node head; // head of list 

	/* Linked list Node*/
	class Node 
	{ 
		int data; 
		Node next; 
		Node(int d) {data = d; next = null; } 
	} 

	void removeDuplicates() 
	{ 
		/*Another reference to head*/
		Node current = head; 

		/* Pointer to store the next pointer of a node to be deleted*/
		Node next_next; 

		/* do nothing if the list is empty */
		if (head == null)	 
			return; 

		/* Traverse list till the last node */
		while (current.next != null) { 

			/*Compare current node with the next node */
			if (current.data == current.next.data) { 
				next_next = current.next.next; 
				current.next = null; 
				current.next = next_next; 
			} 
			else // advance if no deletion 
			current = current.next; 
		} 
	} 
					
	/* Utility functions */

	/* Inserts a new Node at front of the list. */
	public void push(int new_data) 
	{ 
		/* 1 & 2: Allocate the Node & 
				Put in the data*/
		Node new_node = new Node(new_data); 

		/* 3. Make next of new Node as head */
		new_node.next = head; 

		/* 4. Move the head to point to new Node */
		head = new_node; 
	} 

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

	/* Drier program to test above functions */
	public static void main(String args[]) 
	{ 
		LinkedListExample wikitechylist = new LinkedListExample(); 
		wikitechylist.push(63); 
		wikitechylist.push(50); 
		wikitechylist.push(50); 
		wikitechylist.push(42); 
		wikitechylist.push(27); 
		wikitechylist.push(27); 
		
		System.out.println("LinkedList before removal of duplicates"); 
		wikitechylist.printList(); 
		
		wikitechylist.removeDuplicates(); 
		
		System.out.println("LinkedList after removal of elements"); 
		wikitechylist.printList(); 
	} 
} 
JavaScript
LinkedList before removal of duplicates
27 27 42 50 50 63 
LinkedList after removal of elements
27 42 50 63
Markdown

Time Complexity

  • O(n) where n is number of nodes in the given linked list.

Categorized in:

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,