Removing duplicate nodes

Write code to remove duplicate nodes from an unsorted linked list. Keep the original node.

Example 1:

Input: [1, 2, 3, 3, 2, 1] Output: [1, 2, 3] Example 2:

Input: [1, 1, 1, 1, 2] Output: [1, 2] Hint:

The list length is in the range of [0, 20000]. The list elements are in the range [0, 20000]. Advanced:

What if temporary buffers are not allowed?

java

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
    def removeDuplicateNodes(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        r = head
        visited = [head.val]
        while r and r.next:
            if r.next.val not in visited:
                visited.append(r.next.val)
                r = r.next
            else:
                r.next=r.next.next
        return head
Copy the code

python

class Solution:
    def removeDuplicateNodes(self, head: ListNode) -> ListNode:

        if notHead :# If there is nothing in the head, return the head itselfreturn head

        r = head # R is the spokesperson for Head, responsible for iterating and updating, and head is responsible for staying put
        record = {head.val} #record is responsible for storing values seen. The first value is now stored

        while r andR.next: # if r is None, then check if the next item is already in the recordif r.next.val notRecord.add (r.ext.val) # Add the value r = r.ext # to the record and let r go to the next ringelseIf the value of the next ring is already seen, r.next = r.next. Next, the next ring is changed to the next ring"r=r.next"Let r go to the next loop because r.ext has changed, and re-enter the loop to determine if the current r.ext (formerly r.ext.next) has already been encounteredreturn head
Copy the code