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