题目

给定一个未排序的链表，去掉其重复项，并保留原顺序，返回去掉后的列表。

#%%
class LHead:
    def __init__(self):
        self.next = None
    
    def get_ordered_list(self): # 以列表形式打印顺序表
        order_list = []
        if self.next == None or self == None:
            return order_list
        else:
            cur = self.next
            while cur != None:
                order_list.append(cur.data)
                cur = cur.next
            return order_list
        
    def ordered_list_size(self): #获得链表长度      
        return len(self.get_ordered_list())
    
    def create_ordered_list(self,size): #在新建头结点后面生成有序链表
        i = 0
        tmp = None
        cur = self
        ordered_list = []
         #构造单链表
        while i < size:
             tmp = LNode(i)
             tmp.next = None
             cur.next = tmp
             cur = tmp
             i += 1
        cur = self.next
        while cur != None:
            ordered_list.append(cur.data)
            cur = cur.next
        return ordered_list,self
    
#%%
class LNode:
    def __init__(self,data):
        self.data = data
        self.next = None

#%%
def create_unordered_list(list1): #输出值为list1各元素的无序表的表头
    tmp = None
    head = LHead()
    cur = head
     #构造单链表
    for i in range(len(list1)):
         tmp = LNode(list1[i])
         cur.next = tmp
         cur = tmp
    return head

#%%
#def remove_duplicate(head):
#    if head == None or head.next == None:
#        return None
#    else:
#        outter = head.next
#        pre = None
#        while outter.next != None and pre != outter:
#            pre = outter
#            inner = outter.next
#            
#            while inner.next != None:
#                inext = inner.next
#                if outter.data == inner.data:
#                    pre.next = inext
#                    inner.next = None
#                    inner = inext
#                else:
#                    pre = inner
#                    inner = inext
#            if outter.data == inner.data:
#                pre.next = None
#            outter = outter.next
#        if outter.data == inner.data:
#            outter.next = None
#    return head

#%%
# 双循环进行顺序删除
def remove_dup(head):
    if head == None or head.next == None:
        return None
    else:
        outnode = head.next
        
        while outnode != None:
            in_cur = outnode.next
            in_pre = outnode
            while in_cur != None:
                if in_cur.data == outnode.data:
                    in_pre.next = in_cur.next
                    in_cur = in_cur.next
                else:
                    in_pre = in_cur
                    in_cur = in_cur.next
            outnode = outnode.next
    return head

#%%
#递归法进行删除
#利用HashSet进行删除，降低时间复杂度
def remove_dup_hash(head):
    hashset = set()
    if head == None or head.next == None:
        return None
    else:
        cur = head.next
        pre = head
        while cur != None:
            
            if cur.data in hashset:
                cur = cur.next
                pre.next = cur
            else:
                hashset.add(cur.data)
                pre = cur
                cur = cur.next
    return head

            

#%%
list1 = [2,2]
# list = [2,1,4,3,8,9,10]
duplicate_list = create_unordered_list(list1)

#%%
# remove1 = remove_duplicate(duplicate_list)
#a = remove1.get_ordered_list()
#print(a)
remove2 = remove_dup(duplicate_list)
print(remove2)
#%%
b = remove2.get_ordered_list()
print(b)

若为有序链表，则和相邻元素比较即可。