Tagged

Remove Duplicates From Sorted List

Problem Statement

1Problem Description : 
2Given a sorted linked list, delete all duplicates such that each element appear only once
3
4Input: 
5head of the sorted singly linked list
6
7Output: 
8Return head of the linked list after removing all duplicates.

1Example 1 :
2
3  Input : 1 -> 1 -> 2
4
5  Output: 1 -> 2
6
7  Explanation : 
8    As per input list value 1 appeared two times
9    So duplicate node which has value 1 has to be deleted

1Example 2 :
2
3  Input : 1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 5
4
5  Output: 1 -> 2 -> 3 -> 5
6
7  Explanation : As per input values 2 and 3 appeared more that 1 time.

Solution Approaches

By Traversing the list

Prerequisite

LinkedList Data Structure

Algorithm

1Input : head pointer of the sorted singly linked list
2
3Step 0: Initialize current pointer which points to head of the linked list
4
5Step 1: If current and current.next are not null  
6
7Step 2: if current and current.next holds same value, 
8        remove current.next by updating current.next = current.next.next
9
10Step 3: else just move current node by current = current.next 
11
12Step 4: Repeat steps 1 to 3 until we reach end of the linked list
13
14Output : Sorted linked list without duplicate node values.

Example Dry Run

Input : 1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 5

Initialize current pointer at head node of the given linked list

Iteration 1:
- current and current.next are not null
- As current.val ≠ current.next.val, move forward by updating
  current = current.next

Iteration 2 :
- current and current.next are not null
- As current.val = current.next.val, remove current.next by updating
  current.next = current.next.next

Iteration 3 :
- current and current.next are not null
- As current.val ≠ current.next.val => current = current.next

Iteration 4 :
- current and current.next are not null
- As current.val = current.next.val => current.next = current.next.next

Iteration 5 :
- current and current.next are not null
- As current.val = current.next.val => current.next = current.next.next

Iteration 6 :
- current and current.next are not null
- As current.val ≠ current.next.val => current = current.next

Iteration 7 :
- As current.next is null, no more duplicate elements left in the linked list

Output : 1 -> 2 -> 3 -> 5 -> NULL

Code Implementation

Java
Python
Cpp

1public class RemoveDuplicatesInSortedLinkedList {
2
3    // list node class
4    static class ListNode {
5        int val;
6        ListNode next;
7
8        ListNode(int val){
9            this.val = val;
10        }
11    }
12
13    public ListNode removeDuplicates(ListNode head) {
14        // Base case : If head value is null, return null
15        if(head == null) {
16            return null;
17        }
18
19        // Initialize current pointer at head
20        ListNode current = head;
21
22        // Iterate over list and 
23        // compare current node value with next node value
24        while (current.next != null) {
25            // if current node value is equal to next node value
26            // delete next node by updating current.next to current.next.next
27            if(current.val == current.next.val) {
28                current.next = current.next.next;
29            }
30            // if current node value is not equal
31            // just increment current pointer to proceed further
32            else {
33                current = current.next;
34            }
35        }
36        return head;
37    }
38
39    /*  Helper method to construct 
40        linkedList by giving array of values
41    */ 
42    private ListNode constructList(int[] array) {
43        // create dummy head node, this helps to avoid null checks
44        ListNode head = new ListNode(-1);
45        ListNode current = head;
46
47
48        for(int i=0 ; i<array.length; i++){
49            current.next = new ListNode(array[i]);
50            current = current.next;
51        }
52        // as head node pointed to some dummy node ,
53        // head.next is our actual head of the linked list
54        return head.next;
55    }
56
57    // Helper method to print given linked list
58    private void print(ListNode head) {
59        StringBuilder sb = new StringBuilder();
60
61        while(head != null) {
62            sb.append(head.val +" -> ");
63            head = head.next;
64        }
65        sb.append("NULL");
66        System.out.println(sb.toString());
67    }
68
69    // Driver Method
70    public static void main(String[] args) {
71        RemoveDuplicatesInSortedLinkedList obj = 
72        new RemoveDuplicatesInSortedLinkedList();
73        int[] a = {1, 1, 1, 3, 7};
74        ListNode head = obj.constructList(a);
75        ListNode head1New = obj.removeDuplicates(head);
76        obj.print(head1New);
77    }
78
79}

Complexity Analysis

Time Complexity : O(n) where n is the length of the given linked list
Space Complexity : O(1)

DSA Problems

Sorting

Linked List

Merge Two Sorted Linked Lists

k’th Node from End of Linked List

...