Remove Duplicates from Sorted List | Leetcode #83 | Easy

In this post I will discuss the solution to the leetcode problem — Remove Duplicates from Sorted List.

Problem:

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1:

Input: head = [1,1,2]
Output: [1,2]

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

Solution:

This is one of the simplest linked list problems. The idea is to remove duplicate elements from the list and return the list in the same sorted order. The input being a linked list, we always have access to the next element in the list. Let’s use that to form our algorithm for this problem.

1. As a base case, if the input list is empty or has just 1 element then we straightaway return the same as output.
2. Initialize a node current to the input node.
3. Iterate the linked list until the current’s next element is not null. i.e. until the second last element of the list
4. If the current node’s value is equal to the next node’s value, we drop the next node by assigning current.next to current.next.next
5. Otherwise, we move current forward i.e. current = current.next
6. In the end return head as the output.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   int val;
 *   ListNode next;
 *   ListNode() {}
 *   ListNode(int val) { this.val = val; }
 *   ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode deleteDuplicates(ListNode head) {
    if(head == null || head.next == null) {
      return head;
    }
    ListNode current = head;
    while(current.next != null) {
      if (current.val == current.next.val) {
        current.next = current.next.next;
      } else {
        current = current.next;  
      } 
    }
    return head;
  }
}

I hope you enjoyed solving this problem and the solution helps! Happy coding! 🙂

If you think the solution can be improved or misses something, feel free to comment. There is always some room for improvement.

Find the solutions to the leetcode problems here — https://github.com/rishikeshdhokare/leetcode-problems