Remove Duplicates from Sorted List

Description

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 1:
Input: head = [1,1,2]
Output: [1,2]
Explanation: The list 1->1->2 has duplicate value 1. After removing the duplicate, the list becomes 1->2.

Example 2:
Input: head = [1,1,2,3,3]
Output: [1,2,3]
Explanation: The list 1->1->2->3->3 has duplicates at values 1 and 3. After removing duplicates, the list becomes 1->2->3.

Example 3:
Input: head = []
Output: []
Explanation: The empty list remains empty after removing duplicates.

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

Signature

def solution(head: ListNode) -> ListNode: ...

Complexity

Time: O(n)
Space: O(1)

Hints

Pattern: Two pointers / in-place modification
Approach: Use a pointer to traverse. For each node, skip all following nodes with the same value by adjusting next pointers.
Complexity: Single pass through the list in O(n)

Solutions

Python

from typing import Optional


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


def solution(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:
        return head

    slow = head
    fast = head.next

    while fast:
        # print(slow.val, fast.val)

        if slow.val == fast.val:
            # print("Removing ", fast.val)
            slow.next = fast.next
        else:
            slow = fast

        # slow = fast
        fast = fast.next

    # n = head
    # while n:
    #     print(n.val, end=" ")
    #     n = n.next

    return head