Remove Duplicates from Sorted List

Welcome to an in-depth explanation of Leetcode problem 83: Remove Duplicates from Sorted List! In this episode, we delve into an "easy" LeetCode challenge focusing on basic data structures, specifically sorted linked lists. Our task is to efficiently remove any duplicate values from a given sorted linked list, ensuring that each unique value appears exactly once and the list remains sorted. We'll start by exploring the core intuition behind the solution: since the list is already sorted, all duplicates of a particular value will be adjacent. This allows for a straightforward traversal where we compare a current node's value with its next node's value. If they are identical, we've found a duplicate and can remove the next node by rerouting the current node's next pointer to skip over the duplicate. If the values differ, we simply move to the next node. Join us for a step-by-step walkthrough of this classical algorithm, from initialisation of a pointer (cur) to traversing the list and handling duplicates. We'll illustrate the process with a concrete example, showing how a list like 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 4 -> 4 -> 5 transforms into a clean 1 -> 2 -> 3 -> 4 -> 5. Finally, we'll break down the solution's impressive time complexity of O(n) and optimal space complexity of O(1), demonstrating why this approach is highly efficient. Master this essential linked list pattern and enhance your algorithm skills!