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

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

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

This problem uses Linked List, Two Pointers. Understanding these concepts is essential for solving this Medium problem efficiently.

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

Insight 1: Because the list is sorted, duplicates will always appear consecutively. This allows us to easily identify and skip over them. Insight 2: Using a dummy node simplifies the handling of the head of the list, especially if the head needs to be removed during the duplicate removal process.

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

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, Google and 2 more companies.

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

Remove Duplicates from Sorted List II - LeetCode 82 Solution

Q: How to solve Remove Duplicates from Sorted List II?

The solution uses a dummy node to simplify the removal of nodes from the beginning of the list. It iterates through the linked list, checking for consecutive duplicate values. If a duplicate is found, it skips all nodes with that value. If a value is not a duplicate, it advances the 'pred' pointer. The `pred` pointer will point to the node just *before* the first duplicate in a sequence. When a sequence of duplicates is found, we update the `pred->next` pointer to `head`, effectively skipping the duplicates. If no duplicates are found, we move both `head` and `pred` forward.

Remove Duplicates from Sorted List II - Complete Solution Guide

Remove Duplicates from Sorted List II is LeetCode problem 82, a Medium 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 nodes that have duplicate numbers, leaving only distinct numbers from the original list . Return the linked list sorted as well . Example 1: Input: head = [1,2,3,3,4,4,5] Output: [1,2,5] Example 2: Input: head = [1,1,1,2,3] Output: [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

The problem asks us to remove all nodes from a sorted linked list that have duplicate numbers, leaving only distinct numbers from the original list. The input is the head of a sorted linked list, and the output is the head of the modified list with duplicates removed. For example, if the input is [1,2,3,3,4,4,5], the output should be [1,2,5]. The linked list is guaranteed to be sorted in ascending order, and node values are within the range of -100 to 100. We must preserve the sorted order in the output list.

Solution Approach

The solution uses a dummy node to simplify the removal of nodes from the beginning of the list. It iterates through the linked list, checking for consecutive duplicate values. If a duplicate is found, it skips all nodes with that value. If a value is not a duplicate, it advances the 'pred' pointer. The `pred` pointer will point to the node just *before* the first duplicate in a sequence. When a sequence of duplicates is found, we update the `pred->next` pointer to `head`, effectively skipping the duplicates. If no duplicates are found, we move both `head` and `pred` forward.

Step-by-Step Algorithm

Step 1: Create a dummy node and set its 'next' pointer to the head of the original list.
Step 2: Initialize a 'pred' pointer to the dummy node. This pointer will track the node preceding the current 'head' node.
Step 3: Iterate through the linked list using the 'head' pointer.
Step 4: Inside the loop, check if the current node 'head' has a next node and if their values are equal. If they are, we have found a duplicate.
Step 5: If a duplicate is found, store the duplicate value in a variable 'val_to_skip'.
Step 6: Continue moving the 'head' pointer forward until it reaches a node with a different value or the end of the list, skipping all nodes with the duplicate value.
Step 7: Update the 'next' pointer of the 'pred' node to point to the current 'head' node, effectively removing the duplicate nodes from the list.
Step 8: If no duplicate is found (i.e., head.next is null or head.val != head.next.val), move both the 'pred' and 'head' pointers to the next node in the list.
Step 9: Repeat steps 4-8 until the 'head' pointer reaches the end of the list.
Step 10: Return the 'next' pointer of the dummy node, which is the new head of the modified linked list.

Key Insights

Insight 1: Because the list is sorted, duplicates will always appear consecutively. This allows us to easily identify and skip over them.
Insight 2: Using a dummy node simplifies the handling of the head of the list, especially if the head needs to be removed during the duplicate removal process.
Insight 3: We need two pointers to keep track of the previous node (pred) and the current node (head). This allows us to modify the 'next' pointer of the previous node to skip the duplicate nodes.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Linked List, Two Pointers.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, Google, Microsoft, Tencent.

Remove Duplicates from Sorted List II | LeetCode 82

Medium

Linked List Two Pointers

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 dummy = new ListNode(0, head);
        ListNode pred = dummy;

        while (head != null) {
            if (head.next != null && head.val == head.next.val) {
                int val_to_skip = head.val;
                while (head != null && head.val == val_to_skip) {
                    head = head.next;
                }
                pred.next = head;
            } else {
                pred = pred.next;
                head = head.next;
            }
        }

        return dummy.next;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

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

Topics

Linked List Two Pointers

Companies

AdobeAmazonAppleBloombergGoogleMicrosoftTencent

Stats

Difficulty:Medium

Languages:4

Companies:7

Problem #:82

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

10 steps

1
Step 1: Create a dummy node and set its 'next' pointer to the head of the original list.
2
Step 2: Initialize a 'pred' pointer to the dummy node. This pointer will track the node preceding the current 'head' node.
3
Step 3: Iterate through the linked list using the 'head' pointer.
4
Step 4: Inside the loop, check if the current node 'head' has a next node and if their values are equal. If they are, we have found a duplicate.
5
Step 5: If a duplicate is found, store the duplicate value in a variable 'val_to_skip'.
6
Step 6: Continue moving the 'head' pointer forward until it reaches a node with a different value or the end of the list, skipping all nodes with the duplicate value.
7
Step 7: Update the 'next' pointer of the 'pred' node to point to the current 'head' node, effectively removing the duplicate nodes from the list.
8
Step 8: If no duplicate is found (i.e., head.next is null or head.val != head.next.val), move both the 'pred' and 'head' pointers to the next node in the list.
9
Step 9: Repeat steps 4-8 until the 'head' pointer reaches the end of the list.
10
Step 10: Return the 'next' pointer of the dummy node, which is the new head of the modified 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 time complexity is O(n) because in the worst-case scenario (e.g., no duplicates), we traverse the linked list once. Even with duplicates, each node is visited and potentially skipped at most once. The space complexity is O(1) because we only create a constant number of extra variables, regardless of the size of the input linked list.

📖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 approach can also be used to solve this problem. It involves recursively calling the function on the rest of the list. If a duplicate is found, skip all duplicates, and call the function again. Otherwise, return the current node and recursively process the rest of the list.

Time: O(n)Space: O(n) in the worst case, due to recursion depth, where n is the number of nodes. Can be O(1) in best cases.

Trade-offs: The recursive approach might be more readable for some, but it has the overhead of function calls and uses more memory due to the call stack. Iterative approach is generally preferred for its better space efficiency.

✨

Key Insights

1Insight 1: Because the list is sorted, duplicates will always appear consecutively. This allows us to easily identify and skip over them.
2Insight 2: Using a dummy node simplifies the handling of the head of the list, especially if the head needs to be removed during the duplicate removal process.
3Insight 3: We need two pointers to keep track of the previous node (pred) and the current node (head). This allows us to modify the 'next' pointer of the previous node to skip the duplicate nodes.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Linked List

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

Edge Cases

Edge case 1: Empty list (head is None/null). The solution handles this correctly because the `while head:` loop will not execute, and the dummy.next (which is initially head, so None/null) is returned.
Edge case 2: List with all duplicate values (e.g., [1,1,1]). The solution correctly skips all nodes and returns an empty list because pred.next becomes null.
Edge case 3: List with duplicates at the beginning (e.g., [1,1,2,3]). The dummy node helps handle this case smoothly, ensuring that the correct head (2 in this example) is returned.
Edge case 4: List with no duplicates (e.g., [1,2,3]). The algorithm will still function correctly; both `pred` and `head` will move forward one node at a time.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not using a dummy node. Without a dummy node, handling the case where the head of the list needs to be removed becomes more complicated and requires special case handling.

✗Common mistake 2: Incorrectly updating the 'pred' pointer. The 'pred' pointer should only be updated when no duplicates are found. If it's updated within the duplicate skipping loop, the linked list will be broken.

✗Common mistake 3: Not handling the case where 'head' becomes null within the inner loop. This can lead to a null pointer exception when trying to access `head->val` or `head->next`.

✅

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 cleaning and deduplication. This algorithm can be used to remove duplicate entries from a sorted dataset where duplicates are grouped together.

🏦Real-world scenario 2: Database management. When storing sorted data in a database, this algorithm can be used to ensure uniqueness of entries within certain constraints.

🎮Real-world scenario 3: Log processing. Removing redundant log entries (especially those generated in bursts) can make logs easier to analyze and debug.

💡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

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ 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 22, 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

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

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

@CodeNinjaJul 7

❓

Frequently Asked Questions

Why use a dummy node in linked list problems?

A dummy node simplifies edge cases where the head might change (insertion/deletion at head) or when building a new list. Initialize dummy.next = head, work with dummy.next throughout, and return dummy.next at the end to handle all cases uniformly.

When is the two-pointer technique most effective?

Two pointers work best on sorted arrays or when searching for pairs/triplets that satisfy a condition. Common patterns include: moving pointers inward from both ends (like in two-sum variants), fast/slow pointers for cycle detection, or left/right pointers for partitioning.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

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

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

🤖 Need help with this problem?