纯自己思考的结果,花了几个小时,时间和空间消耗的优化超过90%+提交的用户。 我只采用了两个临时的节点。

我的思考是: 一个节点位于重复节点串的前一个节点,另一个节点则是在遍历原始链表 第一个节点的初始化为原始链表的第一个元素,这实际上不能保证它不属于某个连续重复节点串中,但是,它可以在最后被很容易的去除,且不影响之后节点的正确性。

我记录前一个节点的值,并将新节点的值和其比较。因此,在遍历链表的过程中,情况可分为当前节点(即我采用的第二个临时节点)和之前节点的值,相同或不相同两种情况。 我用count参数记录当前节点是否和之前的节点有重复。

第一种情况。如果当前节点和之前的节点的值相同,我们简单的将count加1。不需要改变第一个节点的值。

第二种情况。如果当前节点和之前的节点的值不同。我们需要考虑,当前节点是否为连续相同节点的起点,还是仅仅是普通的不连续的另一个节点。如果是连续节点的起点,则第一个节点不需要动,但是改变count计数从0重新开始。当它是仅仅是普通的不连续的另一个节点,且count数大于0,我们将forenode的next直接连接到当前节点(第二个节点),这就跳过了中间的重复节点。又或者它是仅仅是普通的不连续的另一个节点,且count数等于0。则移动第一个节点,但不需要改变它的next指向,因为不需要跳过连续重复节点。此外,我们的判断总是引用当前节点的next,因此还需要考虑next为None的边界。

class Solution:
    def deleteDuplication(self, pHead: ListNode) -> ListNode:
        # 无节点
        if pHead is None:
            return None
        # 只有一个节点的情况
        elif pHead.next is None:
            return pHead
        # 只有两个节点的情况
        elif pHead.next.next is None:
            if pHead.next.val != pHead.val:
                return pHead
            else:
                return None
        # 三个及以上的节点的情况
        number = pHead.val
        count = 0
        temphead = pHead
        forenode = None

        # 默认选择的第一个forenode节点是否能用,1:能
        if pHead.next.val == pHead.val:
            flag = 0
        else:
            flag = 1

        while temphead is not None:
            # forenode 需要设置为第一个不重复的字符节点上
            # 我的处理是暂时不管,即默认为原始链表的第一个节点
            # 最后,返回新头节点之前,判断一下能不能用(原始链表第一个节点是否重复了)
            # 若不能用,我就从我的新链表的第二个节点开始
            if forenode is None:
                forenode = temphead
                temphead = temphead.next
                continue
            # 第一次遇到不同的字符,要将中间的重复元素去除
            if temphead.val != number:
                # 最后一个元素
                if temphead.next is None:
                    count = 0
                    forenode.next = temphead
                    break
                elif temphead.val != temphead.next.val and count == 0:
                    forenode = temphead
                # 完美的情况,仅一个字符连续相同,即没有多个重复的字符段连在一起
                # 放心的更新节点
                elif temphead.val != temphead.next.val and count > 0:
                    count = 0
                    forenode.next = temphead
                    forenode = temphead
                # 一个字符的连续段后开始新的字符连续段
                # 此时只更新count,number,forenode暂不更新(即便到了最后,因为count!=0,我们的后处理可以
                # 把多个字符重复段一起去除)
                elif temphead.val == temphead.next.val and count > 0:
                    count = 0
                # 碰到了新的字符,无论如何都要更新number
                number = temphead.val
            # 遇到相同的字符
            else:
                count += 1
            temphead = temphead.next

        # 后面的几个字符全部是重复的,或多个连续的重复字符串
        if count > 0:
            forenode.next = None

        if flag == 1:
            return pHead
        else:
            return pHead.next