Remove Duplicates from Sorted List

When working with sorted linked lists, a common challenge is removing duplicate nodes while preserving the original order of distinct elements.

In this article, we will delve into solving the “Remove Duplicates from Sorted List” problem. We will explore the intuition behind the approaches, analyze their time and space complexities, and implement them in JavaScript.

Problem Statement:

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.

---

Approach 1: Iterative

The idea is to identify and remove duplicates in a single pass through the list by updating the next pointer of the current node to skip duplicate nodes, we maintain the original order of distinct elements while eliminating duplicates.

1. Initialize a pointer to the head of the linked list.

2. Iterate through the list by moving the pointer to the next node until the pointer becomes null.

3. At each iteration, compare the current node’s value with the next node’s value.

4. If they are the same, update the current node’s “next” pointer to skip the next node.

5. If they are different, move the pointer to the next node.

6. Repeat these steps until the pointer reaches the end of the list.

7. Finally, return the head of the modified linked list.

// ES6 Arrow Function
const deleteDuplicates = head => {
    let current = head;

    while(current !== null && current.next !== null) {
        if(current.val === current.next.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }

    return head;
}

Time Complexity: O(N)

The algorithm iterates through the entire linked list once, where n is the number of nodes in the list.

Space Complexity: O(1)

No additional data structure is used so the space complexity remains constant.

---

Approach 2: Recursion

1. A recursive function takes a node as a parameter.

2. Check if the node and its next node exist. If not, return the node.

3. If the values of the current node and its next node are equal, update the current node’s “next” pointer to skip the next node.

4. If the values are different, move to the next node and make a recursive call with the next node as the parameter.

5. Return the modified node at each recursion.

// ES6 Arrow Function
const deleteDuplicates = head => {
    if(head === null || head.next === null) return head;
    if(head.val === head.next.val) {
        head.next = head.next.next;
        return deleteDuplicates(head);
    } else {
        head.next = deleteDuplicates(head.next);
        return head;
    }
}

Time Complexity: O(N)

We are performing recursive calls for each node in the linked list. Therefore the time complexity is linear.

Space Complexity: O(N)

Since the space complexity will be determined by the max depth of the recursive call stack. So in the worst case where all nodes are distinct, the maximum depth is N, resulting in linear space complexity.

---

And there you have it guys! We’ve explored two different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem- Leetcode 83