Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0083 - Remove Duplicates from Sorted List
    0083 - Remove Duplicates from Sorted List
    0083 - Remove Duplicates from Sorted List
    0083 - Remove Duplicates from Sorted List

    0083 - Remove Duplicates from Sorted List

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/remove-duplicates-from-sorted-list/

    Solution 1 - Iterative Pointer Traversal

    Traverse the sorted linked list with a pointer. At each node, if the next node has the same value, skip it by updating the next pointer. Otherwise, move to the next node. Since the list is sorted, all duplicates are adjacent.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - Recursive Approach

    Recursively process the list. For each node, recursively remove duplicates from the rest of the list. If the current node's value equals the next node's value, skip the current node by returning head.next. Otherwise, return the current node.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 0083.1 - Remove Duplicates from Sorted List - Solution 1 - Iterative Pointer Traversal """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class ListNode:
    """ListNode Class"""

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """Solution Class"""

    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """Remove Duplicates from Sorted List Function"""
        curr = head

        while curr and curr.next:
            if curr.val == curr.next.val:
                curr.next = curr.next.next
            else:
                curr = curr.next

        return head


#####################################################################################
# Functions
#####################################################################################
def build_list(vals):
    """Helper to build a linked list from a list of values"""
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def print_list(head):
    """Helper to print a linked list"""
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    print(vals)


def testcase():
    """Test Function"""
    print_list(Solution().deleteDuplicates(build_list([1, 1, 2])))          # [1, 2]
    print_list(Solution().deleteDuplicates(build_list([1, 1, 2, 3, 3])))    # [1, 2, 3]
    print_list(Solution().deleteDuplicates(build_list([])))                  # []


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0083.2 - Remove Duplicates from Sorted List - Solution 2 - Recursive Approach """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class ListNode:
    """ListNode Class"""

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """Solution Class"""

    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """Remove Duplicates from Sorted List Function"""
        if not head or not head.next:
            return head

        head.next = self.deleteDuplicates(head.next)

        return head.next if head.val == head.next.val else head


#####################################################################################
# Functions
#####################################################################################
def build_list(vals):
    """Helper to build a linked list from a list of values"""
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def print_list(head):
    """Helper to print a linked list"""
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    print(vals)


def testcase():
    """Test Function"""
    print_list(Solution().deleteDuplicates(build_list([1, 1, 2])))          # [1, 2]
    print_list(Solution().deleteDuplicates(build_list([1, 1, 2, 3, 3])))    # [1, 2, 3]
    print_list(Solution().deleteDuplicates(build_list([])))                  # []


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()