algoadvance

Leetcode 83. Remove Duplicates from Sorted List

Problem Statement

LeetCode 83: Remove Duplicates from Sorted List

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:

Input: head = [1, 1, 2]
Output: [1, 2]

Input: head = [1, 1, 2, 3, 3]
Output: [1, 2, 3]

Clarifying Questions

1. Can the input list be empty?
   • Yes, the input list can be empty. An empty list should return an empty list.
2. Is the list always sorted?
   • Yes, the input list is given to be sorted.
3. Do we need to handle cases with non-integer values?
   • No, the problem specifies that the list will contain integers.

Strategy

1. Initialize a pointer, current, to the head of the linked list.
2. Traverse the list with the current pointer.
3. For each node, check if the value of the current node is the same as the value of the next node (current.next).
4. If it is, skip the next node by setting current.next to current.next.next.
5. If it is not, move current to the next node.
6. Continue this process until the end of the list is reached.
7. Return the head of the modified list.

Code

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // Start from the head of the list
        ListNode current = head;
        
        // Traverse the list
        while (current != null && current.next != null) {
            // Check if current node is the same as next node
            if (current.val == current.next.val) {
                // Skip the next node
                current.next = current.next.next;
            } else {
                // Move to the next node
                current = current.next;
            }
        }
        
        return head;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. Each node is visited once.
• Space Complexity: O(1), since we are not using any extra space proportional to the input size, just a few pointers.

This solution ensures that all duplicate nodes are removed from the sorted list efficiently, maintaining a linear time complexity and a constant space complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?