Understanding LeetCode Problem #83: Removing Duplicates from Sorted Lists

LeetCode problem #83, "Remove Duplicates from Sorted List," is a classic challenge that tests your ability to manipulate linked lists efficiently. In this article, we'll delve into a solution step-by-step.

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

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.
Solution Approach
Let's break down the problem-solving process:

Here is the link of the official.
Link

Understand the input structure

• Analyze the constraints
• Implement the solution
• Optimize and refine
• Understanding the Input Structure
• The input is a singly-linked list node defined as follows:

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

Each node contains a value and a reference to the next node in the list.

Analyzing the constraints

Ths input node is onlh ascending order which means we don't need to care about making it sorted, focusing on finding duplicate and delete it.

Designing an Efficient Algorithm

Our approach will involve a single-pass traversal of the list, identifying and removing duplicate nodes as we go.

Implementing the Solution

Let's look at the implementation:

function deleteDuplicates(head: ListNode | null): ListNode | null {
  let current = head;

  while (current) {
    while (current.next && current.next.val === current.val) {
      current.next = current.next.next;
    }
    current = current.next;
  }

  return head;
}

Let's break down this solution:

Initializing a current pointer to the head of the list. This allows us to modify the next pointers while still having access to the original head.

The outer loop while(current) continues until we reach the end, which means current becomes null.

Inner while loop, while both a)next node is existing and b)value of next node is same as current node, conditions are met, skip the next node. When a duplicate is found, we skip over it by setting current.next = current.next.next.
When one of the conditions becomes false, we move current pointer to the next node.
Finally, we return original head with modified list.

Time and Space Complexity

• Time complexity: O(n), where n is the length of the linked list. We traverse the list once.
• Space complexity: O(1), as we only use a constant amount of space regardless of input size.

Why This Solution Works

Single-pass efficiency: We only need to traverse the list once.
In-place modification: We modify the existing list structure without creating new nodes, optimizing memory usage.
Handling edge cases: Our solution works correctly even for empty lists or lists with no duplicates.
Preserving order: By keeping the first occurrence of each number, we maintain the sorted nature of the list.

Conclusion

Removing duplicates from a sorted linked list is a fundamental problem in algorithm design. This solution demonstrates efficient traversal and manipulation of linked list structures.
Thank you for reading.