Remove Duplicates from Sorted List

šŸ  ā¬…ļø āž”ļø

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]

Example 2:

Input: head = [1,1,2,3,3] Output: [1,2,3]

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.
Note: This problem is from LeetCode.
āŒ Compiled
āŒ Executed
āŒ Correct 
program main
    ! This program solves the problem of deleting all duplicates from a sorted linked list
    ! so that each element appears only once.
    implicit none

    type :: node_t
        integer :: val
        type(node_t), pointer :: next => null()
    end type

    type(node_t), target :: head
    type(node_t), pointer :: curr, prev

    ! Example 1
    call init_list(head)
    call append(head, 1)
    call append(head, 1)
    call append(head, 2)
    print '(A)', 'Example 1:'
    call delete_duplicates(head)
    call print_list(head)

    ! Example 2
    call init_list(head)
    call append(head, 1)
    call append(head, 1)
    call append(head, 2)
    call append(head, 3)
    call append(head, 3)
    print '(A)', 'Example 2:'
    call delete_duplicates(head)
    call print_list(head)

contains

    subroutine init_list(head)
        ! Initialize an empty linked list
        type(node_t), intent(out) :: head

        nullify(head%next)
    end subroutine

    subroutine append(head, val)
        ! Append a new node with value `val` to the end of the linked list
        type(node_t), intent(inout) :: head
        integer, intent(in) :: val
        type(node_t), pointer :: new_node

        allocate(new_node)
        new_node%val = val
        new_node%next => null()

        if (associated(head%next)) then
            ! There are already some nodes in the list
            curr => head
            do while (associated(curr%next))
                curr => curr%next
            end do
            curr%next => new_node
        else
            ! This is the first node in the list
            head%next => new_node
        end if
    end subroutine

    subroutine delete_duplicates(head)
        ! Delete all duplicates from the linked list
        type(node_t), intent(inout) :: head
        type(node_t), pointer :: curr, prev

        curr => head
        prev => null()

        do while (associated(curr%next))
            if (curr%val == curr%next%val) then
                ! Found a duplicate, delete it
                prev%next => curr%next
                deallocate(curr)
                curr => prev
            else
                ! No duplicate found, move on to the next node
                prev => curr
                curr => curr%next
            end if
        end do
    end subroutine

    subroutine print_list(head)
        ! Print the linked list to stdout
        type(node_t), intent(in) :: head
        type(node_t), pointer :: curr

        curr => head
        do while (associated(curr%next))
            write (*, '(I0)') curr%val
            curr => curr%next
        end do
        write (*, '(I0)') curr%val
    end subroutine

end program
āŒ Compiled
āŒ Executed
āŒ Correct 
module linked_list

type :: node
    integer :: val
    type(node), pointer :: next => null()
end type

interface
    pure function delete_duplicates(head) result(new_head)
        type(node), pointer, intent(in) :: head
        type(node), pointer :: new_head
    end function
end interface

contains

pure function delete_duplicates(head) result(new_head)
    type(node), pointer, intent(in) :: head
    type(node), pointer :: current, new_head

    ! Edge case: empty list
    if (.not. associated(head)) then
        nullify(new_head)
        return
    end if

    ! Create a new list with only unique elements
    current => head
    allocate(new_head, source=current)
    current => current%next
    do while (associated(current))
        if (current%val /= new_head%val) then
            allocate(new_head%next, source=current)
            new_head => new_head%next
        end if
        current => current%next
    end do

    ! Sort the list
    call sort_list(new_head)

end function

subroutine sort_list(head)
    type(node), pointer, intent(inout) :: head
    type(node), pointer :: current, next

    current => head
    do while (associated(current))
        next => current%next
        do while (associated(next))
            if (current%val > next%val) then
                call swap(current, next)
            end if
            next => next%next
        end do
        current => current%next
    end do

end subroutine

subroutine swap(a, b)
    type(node), pointer, intent(inout) :: a, b
    type(node), pointer :: temp

    temp => a
    a => b
    b => temp

end subroutine

end module

program main
    use linked_list
    implicit none

    type(node), pointer :: head, current
    integer :: i

    ! Create a linked list with duplicates
    allocate(head)
    head%val = 1
    current => head
    do i = 2, 5
        allocate(current%next)
        current => current%next
        current%val = i
    end do
    current%next => head

    ! Print the original list
    write (*,*) "Original list:"
    current => head
    do while (associated(current))
        write (*,*) current%val
        current => current%next
    end do

    ! Delete duplicates
    head => delete_duplicates(head)

    ! Print the sorted list
    write (*,*) "Sorted list:"
    current => head
    do while (associated(current))
        write (*,*) current%val
        current => current%next
    end do

end program
šŸŒ Data from online sources 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def delete_duplicates(head):
    current = head
    while current and current.next:
        if current.next.val == current.val:
            current.next = current.next.next
        else:
            current = current.next
    return head

The algorithm to delete all duplicates in a sorted linked list simply iterates through the list and compares the value of the current node with the value of the next. If both values are the same, it means that there is a duplicate, so the current node's "next" pointer is updated to point to the node after the duplicate. If the values are different, the algorithm continues iterating to the next node. The process continues until reaching the end of the list. Since the linked list is already sorted, this algorithm guarantees that duplicates will appear consecutively, allowing for their removal in linear time.

šŸŒ Data from online sources 
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* deleteDuplicates(ListNode* head) {
    ListNode* current = head;
    while (current && current->next) {
        if (current->next->val == current->val) {
            ListNode* temp = current->next;
            current->next = temp->next;
            delete temp;
        } else {
            current = current->next;
        }
    }
    return head;
}

The algorithm to delete all duplicates in a sorted linked list simply iterates through the list and compares the value of the current node with the value of the next. If both values are the same, it means that there is a duplicate, so the current node's "next" pointer is updated to point to the node after the duplicate. If the values are different, the algorithm continues iterating to the next node. The process continues until reaching the end of the list. Since the linked list is already sorted, this algorithm guarantees that duplicates will appear consecutively, allowing for their removal in linear time.