83. Remove Duplicates from Sorted List

Problem Description

In this problem, we are provided with the head of a linked list that is already sorted. Our task is to remove any duplicate values from the list. A duplicate is identified when two or more consecutive nodes have the same value. It's important to note that after removing duplicates, the remaining linked list should still be sorted. We must return the modified list with all duplicates deleted, ensuring that each value in the list appears exactly once.

Intuition

The intuition behind the solution comes from the fact that the linked list is already sorted. Since the linked list is sorted, all duplicates of a particular value will be adjacent to each other. We can simply traverse the linked list from the head to the end, and for each node, we check if its value is the same as the value of the next node. If it is, we have found a duplicate, and we need to remove the next node by changing pointers. We update the current node's next pointer to the next node's next pointer, effectively skipping over the duplicate node and removing it from the list. If the values are not identical, we move on to the next node. We repeat this process until we have checked all nodes. The given Python code implements this approach by using a while loop that continues as long as there are more nodes to examine (cur and cur.next are not None).

Learn more about Linked List patterns.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Solution Approach

The implementation of the solution involves a classical algorithm for removing duplicates from a sorted linked list. The algorithm utilizes the fact that a linked list allows for efficient removal of a node by simply rerouting the next pointer of the previous node.

Here's a step-by-step explanation of how the given Python code works:

Step 1: Initialize

A pointer named cur is initialized to point to the head of the linked list.

Step 2: Traverse the Linked List

We use a while loop to go through the linked list. The loop runs as long as cur is not None (indicating that we haven't reached the end of the list) and cur.next is not None (indicating that there is at least one more node to examine for potential duplicates).

while cur and cur.next:

Step 3: Check for Duplicates

Inside the loop, we compare the current node's value cur.val with the value of the next node cur.next.val.

Step 4: Remove Duplicates

If cur.val equals cur.next.val, we've found a duplicate. Instead of removing the current node, which would be more challenging, we remove the next node. This is accomplished by updating the next pointer of cur to skip the next node and point to the following one:

if cur.val == cur.next.val:
    cur.next = cur.next.next

This effectively removes the duplicate node from the list without disturbing the rest of the list's structure.

Step 5: Move to the Next Distinct Element

If no duplicate was found (the else branch), we simply move the pointer cur to the next node to continue the process:

else:
    cur = cur.next

Step 6: Return the Updated List

Once the loop is finished (meaning we've reached the end of the list or there are no more items in the linked list), we return the head of the list, which now points to the updated, duplicate-free sorted linked list.

Using this simple yet effective approach, we ensure that the list stays sorted, as we're only removing nodes and not altering the order of the remaining nodes.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the following sorted linked list where some values are duplicated:

1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 4 -> 4 -> 5

We want to remove the duplicate values so that each number is unique in the list.

Step 1: Initialize

We start with a pointer cur pointing to the head (the node with value 1).

Step 2: Traverse the Linked List

Since cur (1) and cur.next (2) are not None, we enter the while loop.

Step 3: Check for Duplicates

We compare cur.val (1) with cur.next.val (2). They are different, so we move to the next node.

Step 4: Is there a Duplicate?

Now cur points to the node with value 2.
We compare cur.val (2) with cur.next.val (also 2). This time they are the same, signaling a duplicate.

Step 5: Remove Duplicates

We update cur.next to point to cur.next.next. The duplicate node with value 2 is now skipped.
The linked list now looks like this: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 4 -> 5.

Step 6: Continue Traversing

The loop continues, and now cur points to the node with value 2, and cur.next points to the node with value 3, which is distinct. We move to the next node.

Step 7: Repeat Steps 3 to 5

Now cur points to the node with value 3, and we find that cur.next.val is also 3. We remove the duplicate as before.
The linked list now looks like: 1 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5.
We continue this process for the remaining nodes with value 4 and finally remove all duplicates.

Step 8: Final Linked List After the while loop finishes, we've removed all duplicates, and our final linked list looks like this:

1 -> 2 -> 3 -> 4 -> 5

Step 9: Return the Updated List

With no more duplicates left to remove, we exit the while loop and return the head of the updated list, which is the reference to the first node in our duplicate-free, sorted linked list.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, value=0, next_node=None):
4        self.value = value
5        self.next_node = next_node
6
7class Solution:
8    def deleteDuplicates(self, head: ListNode) -> ListNode:
9        """Remove all duplicates from a sorted linked list such that 
10        each element appears only once and return the modified list."""
11      
12        # Initialize current to point to the head of the list
13        current = head
14      
15        # Traverse the linked list
16        while current and current.next_node:
17            # If the current value is equal to the value in the next node
18            if current.value == current.next_node.value:
19                # Bypass the next node as it's a duplicate
20                current.next_node = current.next_node.next_node
21            else:
22                # Move to the next unique value if no duplicate is found
23                current = current.next_node
24              
25        # Return the head of the updated list
26        return head
27

1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5    int val;        // Value of the node
6    ListNode next;  // Reference to the next node in the list
7
8    // Constructor to create a node with no next node
9    ListNode() {}
10
11    // Constructor to create a node with a given value
12    ListNode(int val) { this.val = val; }
13
14    // Constructor to create a node with a given value and next node
15    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
16}
17
18class Solution {
19    /**
20     * Deletes all duplicates such that each element appears only once.
21     *
22     * @param head The head of the input linked list.
23     * @return The head of the linked list with duplicates removed.
24     */
25    public ListNode deleteDuplicates(ListNode head) {
26        // Initialize current to the head of the linked list
27        ListNode current = head;
28
29        // Iterate over the linked list
30        while (current != null && current.next != null) {
31            // If the current node's value is equal to the value of the next node, skip the next node
32            if (current.val == current.next.val) {
33                current.next = current.next.next;
34            } else { // Otherwise, move to the next node
35                current = current.next;
36            }
37        }
38
39        // Return the head of the modified list
40        return head;
41    }
42}
43

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    // Function to delete duplicate elements from a sorted linked list
14    ListNode* deleteDuplicates(ListNode* head) {
15        ListNode* current = head; // Create a pointer to iterate through the list
16
17        // Continue iterating as long as the current node and its successor are not null
18        while (current != nullptr && current->next != nullptr) {
19            if (current->val == current->next->val) {
20                // If the current node's value equals the next node's value, skip the next node
21                current->next = current->next->next;
22            } else {
23                // Otherwise, move to the next node
24                current = current->next;
25            }
26        }
27
28        // Return the head of the modified list
29        return head;
30    }
31};
32

1/**
2 * Definition for singly-linked list node.
3 */
4interface ListNode {
5  val: number;
6  next: ListNode | null;
7}
8
9/**
10 * Deletes all duplicates such that each element appears only once.
11 * @param {ListNode | null} head - The head of the linked list.
12 * @return {ListNode | null} The modified list head with duplicates removed.
13 */
14const deleteDuplicates = (head: ListNode | null): ListNode | null => {
15    let currentNode: ListNode | null = head;
16
17    // Loop through the list while the current node and the next node are not null
18    while (currentNode && currentNode.next) {
19        // Compare the current node value with the next node value
20        if (currentNode.val === currentNode.next.val) {
21            // If they are equal, skip the next node by pointing to node after next.
22            currentNode.next = currentNode.next.next;
23        } else {
24            // If they are not equal, move to the next node
25            currentNode = currentNode.next;
26        }
27    }
28
29    // Return the head of the modified list
30    return head;
31};
32

Time and Space Complexity

The time complexity of the provided code is O(n), where n is the number of nodes in the linked list. This is because it involves a single traversal through all the nodes of the list, and for each node, it performs a constant amount of work by checking if the next node has a duplicate value and potentially skipping over duplicates.

The space complexity of the code is O(1), as it only uses a fixed amount of additional memory for the cur pointer. No extra space proportional to the size of the input is needed, whatever the size of the linked list is.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know