【数据结构与算法】【LeetCode】【链表】82. 删除排序链表中的重复元素 II

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def createLink_rearinsert(lista):
    head = ListNode(-1)
    rear = head
    for i in lista:
        new_node=ListNode(i)
        rear.next=new_node
        rear=new_node
    return head.next
class Solution():
    def deleteDuplicates(self, head):
        if not (head and head.next):
            return head
        # 用哈希表记录每个节点值的出现频率
        d = dict()
        p = head
        arr = []
        while p:
            val = p.val
            d[val] = d.setdefault(val,0)+1
            p = p.next
        # 将所有只出现一次的值放到arr中，之后再对这个arr排序
        for k in d:
            if d[k]==1:
                arr.append(k)
        arr = sorted(arr)
        dummy = ListNode(-1)
        p = dummy
        # 创建长度为len(arr)长度的链表，依次将arr中的值赋给每个链表节点
        for i in arr:
            tmp = ListNode(i)
            p.next = tmp
            p = p.next
        return dummy.next
if __name__=="__main__":
    a=[-1,1,1,2,4]
    new_a=createLink_rearinsert(a)
    a1 = Solution()
    p=a1.deleteDuplicates(new_a)
    list1=[]
    while(p!=None):
        list1.append(p.val)
        #print(p.val)
        p=p.next
    print(list1)

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def createLink_rearinsert(lista):
    head = ListNode(-1)
    rear = head
    for i in lista:
        new_node=ListNode(i)
        rear.next=new_node
        rear=new_node
    return head.next
class Solution(object):
    def deleteDuplicates(self, head):
        if not (head and head.next):
            return head
        dummy = ListNode(-1)
        dummy.next = head
        a = dummy
        b = head
        while b and b.next:
            # 初始化的时a指向的是哑结点，所以比较逻辑应该是a的下一个节点和b的下一个节点
            if a.next.val!=b.next.val:
                a = a.next
                b = b.next
            else:
                # 如果a、b指向的节点值相等，就不断移动b，直到a、b指向的值不相等 
                while b and b.next and a.next.val==b.next.val:
                    b = b.next
                a.next = b.next
                b = b.next
        return dummy.next

if __name__=="__main__":
    a=[-1,1,1,2,4]
    new_a=createLink_rearinsert(a)
    a1 = Solution()
    p=a1.deleteDuplicates(new_a)
    list1=[]
    while(p!=None):
        list1.append(p.val)
        #print(p.val)
        p=p.next
    print(list1)

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def createLink_rearinsert(lista):
    head = ListNode(-1)
    rear = head
    for i in lista:
        new_node=ListNode(i)
        rear.next=new_node
        rear=new_node
    return head.next
class Solution(object):
    def deleteDuplicates(self, head):
        if not (head and head.next):
            return head
        dummy = ListNode(-1)
        dummy.next = head
        a = dummy
        b = head.next
        while b:
            if a.next.val!=b.val:
                a = a.next
                b = b.next
            else:
                while b and a.next.val==b.val:
                    b = b.next
                # 这里的去重跟解法二有点差别，解法二的是
                # a.next = b.next
                a.next = b
                # b指针在while中判断完后，可能指向了null，这里需要处理边界问题
                b = b.next if b else None
        return dummy.next

if __name__=="__main__":
    a=[-1,1,1,2,4]
    new_a=createLink_rearinsert(a)
    a1 = Solution()
    p=a1.deleteDuplicates(new_a)
    list1=[]
    while(p!=None):
        list1.append(p.val)
        #print(p.val)
        p=p.next
    print(list1)