Samsung device software may store ordered event identifiers in a singly linked list. Given the head of the list, remove every node whose value has appeared earlier, preserving the first occurrence and the original order of remaining nodes.
The removal must be performed in place: do not create replacement nodes and do not use a hash set, dictionary, array, or other collection to track values. Return the original head of the modified list, or None if the list is empty.
The input is head, either None or a reference to a singly linked list whose nodes have integer field val and pointer field next. The function returns the head reference of the deduplicated list. For examples and test cases, lists are shown as arrays, and the evaluator converts them to linked-list nodes before calling the function.
def remove_duplicates(head):