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();
}
}
LinkedList before removal of duplicates
27 27 42 50 50 63
LinkedList after removal of elements
27 42 50 63

Time Complexity

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

Categorized in:

Tagged in:

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