Leetcode 83. Remove Duplicates from Sorted List

Problem Description

The problem is asking to remove any duplicate element from the given sorted linked list. We are given a sorted linked list. The list may contain multiple duplicates so we need to remove those duplicates such that each element appears only once.

Let's take an example to understand the problem:

If the given sorted linked list is: 1->1->2, after removing the duplicates, the linked list should look like this: 1->2.

Solution Approach

A simple straight-forward approach can be used to solve this problem.

The approach used here is to iterate over the linked list. If we find that the current node’s value is the same as the next node’s value, we change the next pointer of current node to next to next node.

For example, if our list is: 1->1->2->3->3

We start from the head, 1. The next node's value (1) is the same as the current node’s value, so we point the next of current node to the next to next node (1->2->3->3) and continue this till the list end.

Here is the pseudo code for the solution:

  1. Initialize the current node as head.
  2. Loop through the linked list till current is not null: a. If current node's value is equal to the next node's value, set current node's next as next to next node. b. Else, move to the next node by updating current node to current's next.
  3. Return the head of the list as the final list will still have the same head.

Now, let's write the code in five different programming languages.

Solution in Python

3class Solution:
4    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
5        current = head
6        while current:
7            while current.next and current.val == current.next.val:
8                current.next = current.next.next
9            current = current.next
10        return head

Solution in Java

3class Solution {
4    public ListNode deleteDuplicates(ListNode head) {
5        ListNode current = head;
6        while (current != null && current.next != null) {
7            if (current.next.val == current.val) {
8                current.next = current.next.next;
9            } else {
10                current = current.next;
11            }
12        }
13        return head;
14    }

Solution in JavaScript

3var deleteDuplicates = function(head) {
4    let current = head;
5    while(current && current.next){
6        if(current.next.val === current.val){
7            current.next = current.next.next;
8        }else{
9            current = current.next;
10        }
11    }
12    return head;

Solution in C++

3class Solution {
5    ListNode* deleteDuplicates(ListNode* head) {
6        ListNode* current = head;
7        while (current && current->next) {
8            if (current->next->val == current->val) {
9                current->next = current->next->next;
10            } else {
11                current = current->next;
12            }
13        }
14        return head;
15    }

Solution in C#

3public class Solution {
4    public ListNode DeleteDuplicates(ListNode head) {
5        ListNode curr = head;
6        while (curr != null && curr.next != null)
7        {
8            if (curr.next.val == curr.val) curr.next = curr.next.next;
9            else curr = curr.next;
10        }
11        return head;
12    }

In this problem, understanding the data structure being used, namely a linked list, and how to manipulate its nodes are crucial. The provided solutions in Python, Java, JavaScript, C#, and C++ implement the same logic and approach. Understanding one of them ensures you can grasp the others, since the main difference is essentially the syntax of each language.

This problem emphasizes the importance of understanding not only simple data types, but also complex ones, like linked lists and trees, along with mastering the manipulation and traversal methodologies of these structures. From removing duplicates to sorting and reversing lists, these are all operations that are fundamental in technical interviews and real world problems.

To master linked lists, try to solve more problems from different sources and different levels. You can find plenty of problems on websites such as LeetCode, HackerRank, and Codewars. Always attempt to solve problems independently first, then review best practices and compare them with your solution. Coding is a skill that improves with practice.

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

TA 👨‍🏫