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)

SpaceComplexity: O(1)

""" 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()

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)

SpaceComplexity: O(n)

""" 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()

0083 - Remove Duplicates from Sorted List

Solution 1 - Iterative Pointer Traversal

Solution 2 - Recursive Approach