题解 | #删除链表中重复的结点#

纯自己思考的结果，花了几个小时，时间和空间消耗的优化超过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