What is the time complexity of Remove Duplicates from Sorted List?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Remove Duplicates from Sorted List?

This problem uses Linked List. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Remove Duplicates from Sorted List?

**Leveraging Sortedness for Adjacency Checks**: The fundamental insight is that because the list is sorted, any duplicates will always be directly next to each other. This eliminates the need for auxiliary data structures like hash sets or complex look-ahead logic; a simple `current.val == current.next.val` comparison is sufficient. **In-place Pointer Rewiring**: The solution cleverly re-wires `next` pointers to 'skip' duplicate nodes. When `current.val` matches `current.next.val`, assigning `current.next = current.next.next` effectively removes `current.next` from the list's chain without allocating new memory or shifting elements. This operation also naturally handles consecutive duplicates (e.g., `1,1,1`) by allowing `current` to stay put and re-evaluate its *new* next node against its own value.

Which companies ask LeetCode 83. Remove Duplicates from Sorted List in interviews?

This problem is frequently asked at Accenture, Adobe, Amazon, Apple, Bloomberg and 4 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Remove Duplicates from Sorted List - LeetCode 83 Solution

Q: How to solve Remove Duplicates from Sorted List?

The provided solution leverages the 'sorted list' property to its fullest. It employs a single `current` pointer that traverses the list. The core idea is simple: because all duplicates will appear consecutively, we only need to compare `current.val` with `current.next.val`. If they are identical, we've found a duplicate (`current.next` is the duplicate). Instead of advancing `current` to this duplicate, we effectively 'delete' it by making `current.next` point to `current.next.next`, thereby bypassing the duplicate node. `current` remains in its position, ready to check if the *new* `current.next` is also a duplicate of `current.val` (which handles cases like `1,1,1`). If `current.val` and `current.next.val` are different, it means `current.val` is unique at this point, so we safely advance `current` to `current.next` and continue our scan. This process repeats until `current` or `current.next` becomes `None`, indicating the end of the list or no more pairs to compare.

Remove Duplicates from Sorted List - Complete Solution Guide

Remove Duplicates from Sorted List is LeetCode problem 83, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 . 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.

Detailed Explanation

You're presented with a linked list, but with a crucial guarantee: it's already perfectly sorted in ascending order. Your task is to modify this list in-place so that every value appears only once. For instance, if you're handed `[1,1,2]`, your output should be `[1,2]`. Similarly, an input like `[1,1,2,3,3]` needs to become `[1,2,3]`. The final list, of course, must remain sorted.

Solution Approach

The provided solution leverages the 'sorted list' property to its fullest. It employs a single `current` pointer that traverses the list. The core idea is simple: because all duplicates will appear consecutively, we only need to compare `current.val` with `current.next.val`. If they are identical, we've found a duplicate (`current.next` is the duplicate). Instead of advancing `current` to this duplicate, we effectively 'delete' it by making `current.next` point to `current.next.next`, thereby bypassing the duplicate node. `current` remains in its position, ready to check if the *new* `current.next` is also a duplicate of `current.val` (which handles cases like `1,1,1`). If `current.val` and `current.next.val` are different, it means `current.val` is unique at this point, so we safely advance `current` to `current.next` and continue our scan. This process repeats until `current` or `current.next` becomes `None`, indicating the end of the list or no more pairs to compare.

Step-by-Step Algorithm

Step 1: Initialize a pointer `current` to the head of the linked list.
Step 2: Iterate through the list using a `while` loop, continuing as long as `current` is not `null` and `current.next` is not `null`.
Step 3: If `current.val` is equal to `current.next.val`, remove the duplicate node by updating `current.next` to point to `current.next.next`. This effectively skips the duplicate node.
Step 4: If `current.val` is not equal to `current.next.val`, move to the next node by setting `current = current.next`.
Step 5: Return the modified `head` of the linked list.

Key Insights

**Leveraging Sortedness for Adjacency Checks**: The fundamental insight is that because the list is sorted, any duplicates will always be directly next to each other. This eliminates the need for auxiliary data structures like hash sets or complex look-ahead logic; a simple `current.val == current.next.val` comparison is sufficient.
**In-place Pointer Rewiring**: The solution cleverly re-wires `next` pointers to 'skip' duplicate nodes. When `current.val` matches `current.next.val`, assigning `current.next = current.next.next` effectively removes `current.next` from the list's chain without allocating new memory or shifting elements. This operation also naturally handles consecutive duplicates (e.g., `1,1,1`) by allowing `current` to stay put and re-evaluate its *new* next node against its own value.
**Single Pass, Constant Space Efficiency**: The algorithm traverses the linked list exactly once, examining each node a constant number of times. This results in an optimal time complexity of O(N), where N is the number of nodes. Furthermore, since it only uses a single pointer (`current`) and modifies the list directly, its space complexity is O(1), making it highly efficient for memory-constrained environments.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Linked List.

Companies

Asked at: Accenture, Adobe, Amazon, Apple, Bloomberg, Microsoft, Nvidia, Oracle, Revolut.

Remove Duplicates from Sorted List | LeetCode 83

Easy

Linked List

Time: O(n)Space: O(1)

Solution Code

Available in:

/**
 * 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) {
        ListNode 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;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 83: Remove Duplicates from Sorted List - Detailed explanation and solution approaches.

Topics

Linked List

Companies

AccentureAdobeAmazonAppleBloombergMicrosoftNvidiaOracle

Stats

Difficulty:Easy

Languages:4

Companies:9

Problem #:83

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize a pointer `current` to the head of the linked list.
2
Step 2: Iterate through the list using a `while` loop, continuing as long as `current` is not `null` and `current.next` is not `null`.
3
Step 3: If `current.val` is equal to `current.next.val`, remove the duplicate node by updating `current.next` to point to `current.next.next`. This effectively skips the duplicate node.
4
Step 4: If `current.val` is not equal to `current.next.val`, move to the next node by setting `current = current.next`.
5
Step 5: Return the modified `head` of the linked list.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The algorithm iterates through the linked list once, performing a constant amount of work at each node. Therefore, the time complexity is linear, O(n), where n is the number of nodes in the list. The algorithm modifies the list in-place, using only a constant amount of extra space for the `current` pointer. Hence, the space complexity is O(1).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursive Approach

A recursive solution can also be implemented. The base cases would be an empty list or a list with one node. The recursive step would compare the current node's value with the next node's value and recursively call the function on the rest of the list after handling duplicates.

Time: O(n)Space: O(n) (due to recursive call stack)

Trade-offs: While functionally equivalent, the recursive approach has a higher space complexity due to the recursive call stack, which can grow proportionally to the length of the list in the worst case. The iterative approach is generally preferred for its constant space complexity.

✨

Key Insights

1**Leveraging Sortedness for Adjacency Checks**: The fundamental insight is that because the list is sorted, any duplicates will always be directly next to each other. This eliminates the need for auxiliary data structures like hash sets or complex look-ahead logic; a simple `current.val == current.next.val` comparison is sufficient.
2**In-place Pointer Rewiring**: The solution cleverly re-wires `next` pointers to 'skip' duplicate nodes. When `current.val` matches `current.next.val`, assigning `current.next = current.next.next` effectively removes `current.next` from the list's chain without allocating new memory or shifting elements. This operation also naturally handles consecutive duplicates (e.g., `1,1,1`) by allowing `current` to stay put and re-evaluate its *new* next node against its own value.
3**Single Pass, Constant Space Efficiency**: The algorithm traverses the linked list exactly once, examining each node a constant number of times. This results in an optimal time complexity of O(N), where N is the number of nodes. Furthermore, since it only uses a single pointer (`current`) and modifies the list directly, its space complexity is O(1), making it highly efficient for memory-constrained environments.

📚

Key Terms Explained

For Students

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Edge Cases

Edge case 1: Empty list (head == null): The `while` loop condition handles this case gracefully; the loop doesn't execute, and the function returns the empty list.
Edge case 2: List with all duplicates (e.g., [1,1,1,1]): The algorithm correctly removes all but the first node, resulting in a list with only one node.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the edge case of an empty list. The code should explicitly check for `head == null` before starting the iteration.

✗Common mistake 2: Incorrectly handling memory deallocation in languages like C. When removing a node, it is important to free the memory occupied by the removed node to prevent memory leaks (as shown in the provided C solution).

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data deduplication in databases: This algorithm can be adapted for removing duplicate entries from a sorted database table efficiently, reducing storage space and improving query performance.

🏦Real-world scenario 2: Stream processing: In scenarios where data arrives as a sorted stream (e.g., sensor readings in ascending order of time), this algorithm can filter out duplicate readings efficiently as the stream is processed.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The dummy node technique prevents edge cases. For cycle detection, Floyd's algorithm is the standard. Always handle empty list and single node cases.

🎯 Interview Tip

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

Losing reference to nodes when modifying pointers. Use temporary variables to save references.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 23, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 29

❓

Frequently Asked Questions

How does the fast/slow pointer technique work?

Fast pointer moves 2 steps while slow moves 1 step. When fast reaches the end, slow is at middle. If there's a cycle, they will meet. This technique is used for: finding middle node, detecting cycles, finding cycle start point, and checking palindromes.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Remove Duplicates from Sorted List"?

For this easy-level Linked List problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether standard techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?