In this tutorial, I am going to discuss a programming question to remove duplicates from a sorted linked list.
Given a sorted linked list, write a code to remove all duplicates such that each element appears only once.
For example:
Input:
1 -> 2 -> 2 -> 3 -> 3 -> NULL
Output:
1 -> 2 -> 3 -> NULL
This problem is similar to remove duplicates from a sorted and unsorted array.
Remove duplicates from an unsorted array
Let’s first discuss the algorithm to delete duplicate-value nodes from a sorted linked list then we’ll write it’s java code.
Programming Questions on Linked List
How to Remove Duplicates from a Linked List?
To remove duplicates from a linked list, traverse a linked list from the head node. While traversing compare each node value with its next node value. If the value is same for both the nodes then skip the next node and point the next pointer of the current node to the one after the next node.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//Remove duplicates from a linked list public Node removeDuplicates(Node head) { Node temp = head; //Traverse a linked list while(temp != null && temp.next != null) { //Compare data of the node to it's next node if(temp.data == temp.next.data) { //Point next node pointer temp.next = temp.next.next; } else { temp = temp.next; } } return head; } |
The time complexity of this approach is O(n) and it’s space complexity is O(1).
Find the middle element of a linked list
Remove Duplicates from a Sorted Linked List – Java Code
We have discussed the logic to remove duplicates from a linked list. Let’s write it’s java code.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
public class RemoveDuplicateFromSortedLinkedList { private Node head; public RemoveDuplicateFromSortedLinkedList() { this.head = null; } public Node removeDuplicates() { Node temp = head; while(temp != null && temp.next != null) { if(temp.data == temp.next.data) { temp.next = temp.next.next; } else { temp = temp.next; } } return head; } public static void main(String[] args) { RemoveDuplicateFromSortedLinkedList ll = new RemoveDuplicateFromSortedLinkedList(); ll.insertAtEnd(1); ll.insertAtEnd(2); ll.insertAtEnd(2); ll.insertAtEnd(3); ll.insertAtEnd(3); ll.insertAtEnd(4); ll.insertAtEnd(5); ll.print(); System.out.println("\n"); ll.removeDuplicates(); ll.print(); } public void print() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } } public Node insertAtEnd(int data) { if (head == null) { head = new Node(data); } else { Node node = head; while(node.next != null) { node = node.next; } //Points to new node node.next = new Node(data); } return head; } } |
Remove Duplicates from Sorted List – LeetCode Solution
The logic i have already discussed. Let’s write a solution for LeetCode problem to delete duplicates from sorted list.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//Delete Duplicates from Sorted Linked List - Java Code public ListNode deleteDuplicates(ListNode head) { ListNode temp = head; while(temp!= null && temp.next!= null) { if(temp.val == temp.next.val) { temp.next = temp.next.next; } else { temp = temp.next; } } return head; } |
Remove Duplicates from Sorted List – InterviewBit Solution
In this example, I have discussed remove duplicates from sorted list InterviewBit solution.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public ListNode deleteDuplicates(ListNode A) { ListNode temp = A; while(temp != null && temp.next != null) { if(temp.val == temp.next.val) { temp.next = temp.next.next; } else { temp = temp.next; } } return A; } |
In this video tutorial, I have explained the algorithm and it’s java code to delete duplicates from sorted linked list.
