Tagged
• DSA Problems
• Sorting
• Linked List
•

# Problem Statement

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

```1Example 1 :2
3  Input : 1 -> 1 -> 24
5  Output: 1 -> 26
7  Explanation : 8    As per input list value 1 appeared two times9    So duplicate node which has value 1 has to be deleted```

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

# By Traversing the list

## Algorithm

```1Input : head pointer of the sorted singly linked list2
3Step 0: Initialize current pointer which points to head of the linked list4
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.next9
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 list13
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

1. Java
2. Python
3. Cpp

```1public class RemoveDuplicatesInSortedLinkedList {2
3    // list node class4    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 null15        if(head == null) {16            return null;17        }18
19        // Initialize current pointer at head20        ListNode current = head;21
22        // Iterate over list and 23        // compare current node value with next node value24        while (current.next != null) {25            // if current node value is equal to next node value26            // delete next node by updating current.next to current.next.next27            if(current.val == current.next.val) {28                current.next = current.next.next;29            }30            // if current node value is not equal31            // just increment current pointer to proceed further32            else {33                current = current.next;34            }35        }36        return head;37    }38
39    /*  Helper method to construct 40        linkedList by giving array of values41    */ 42    private ListNode constructList(int[] array) {43        // create dummy head node, this helps to avoid null checks44        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 list54        return head.next;55    }56
57    // Helper method to print given linked list58    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 Method70    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
•
...