剑指offer——在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点， # 重复的结点不保留，返回链表头指针。

布满荆棘的人生 2022-05-19 05:29 115阅读 0赞

# 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，
    # 重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
    # -*- coding:utf-8 -*-
    class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    class Solution:
        # 需要注意的是，最后一个节点，它的next为空，因此最后的重复节点集合为None，上一个节点（不重复）加入了nodes，不重复直接删掉
        def deleteDuplication(self, pHead):
            node_list = [] #保存相同的节点
            nodes = [] #保存不重复的节点
            p = pHead
            node_list = [p]
            while p != None:
                p1 = p.next
                if p1 != None and p1.val == p.val:
                    node_list.append(p1) # 当前后节点相等，将后一个节点添加到重复节点集合中
                if p1 == None or p1.val != p.val:
                    if len(node_list) == 1:
                        nodes.append(p) # 当前前后节点不同，看看前一个节点的重复节点集合中有几个元素，如果只有一个，认为前一个节点为有效节点
                    node_list = [p1] #将后一个节点作为重复节点集合的初始值
                p = p1
            if len(nodes) == 0:
                return None
            nodes.append(None)
            for k in range(len(nodes)-1):
                nodes[k].next = nodes[k+1]
            return nodes[0]
    a1=ListNode(1)
    a2=ListNode(2)
    a3=ListNode(3)
    a4=ListNode(4)
    a5=ListNode(5)
    a1.next=a2
    a2.next=a3
    a3.next=a4
    a4.next=a5       
    S = Solution()
    S.deleteDuplication(a1)