Amazon Prime




 
Tagged
  • DSA Problems
  • Sorting
  • Linked List
  •  

    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.

    RemoveDuplicatesFromSortedList - Example

    Solution Approaches

    By Traversing the list

    Prerequisite

    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

      RemoveDuplicatesFromSortedList - Input

     
    • Iteration 1:

      • current and current.next are not null

      • As current.val ≠ current.next.val, move forward by updating

        current = current.next

      RemoveDuplicatesFromSortedList - Iteration1

     
    • 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

      RemoveDuplicatesFromSortedList - Iteration2

     
    • Iteration 3 :

      • current and current.next are not null
      • As current.val ≠ current.next.val => current = current.next

      RemoveDuplicatesFromSortedList - Iteration3

     
    • Iteration 4 :

      • current and current.next are not null
      • As current.val = current.next.val => current.next = current.next.next

      RemoveDuplicatesFromSortedList - Iteration4

     
    • Iteration 5 :

      • current and current.next are not null
      • As current.val = current.next.val => current.next = current.next.next

      RemoveDuplicatesFromSortedList - Iteration5

     
    • Iteration 6 :

      • current and current.next are not null
      • As current.val ≠ current.next.val => current = current.next

      RemoveDuplicatesFromSortedList - Iteration6

     
    • Iteration 7 :

      • As current.next is null, no more duplicate elements left in the linked list

      RemoveDuplicatesFromSortedList - Iteration7

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

    Code Implementation

    1. Java
    2. Python
    3. 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
  •  
    ...