LeetCode 删除链表中的重复元素

谁借莪１个温暖的怀抱￠ 2023-07-10 14:11 131阅读 0赞

删除单向链表的节点，需要记录前驱节点。链表的操作就是改变指针的指向。  
第一种情况，删除所有的重复元素，使得最终每个元素只出现一次。比如输入:1->1->2，输出：1->2。因为需要比较相邻节点，而且需要保留一个重复的节点，所以用两个指针即可，一个指针记录前驱节点，一个指针记录下一个节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70]

class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            pre = head  #前驱节点
            while pre:
                fast = pre.next  #下一个节点
                if fast:
                    if pre.val == fast.val:  #出现重复元素
                        while fast:  #从fast节点开始，向后找到第一个不同元素
                            if fast.val != pre.val:
                                break
                            fast = fast.next
                        pre.next = fast  #前驱节点pre直接指向当前fast，删除中间所有重复的元素，只留下一个，即pre所指向的节点
                    else:
                        pre = pre.next
                else:   #fast为空，说明已经到了尾节点
                    return head
            return head

第二种情况：删除所有重复数字的节点，只保留没有重复出现的节点。比如输入：1->1->1->2->3，输出：2->3。  
这时候用两个指针就不行了，需要用到三个指针，一个同样是记录前驱节点的pre指针，一个是慢指针slow=pre.next，一个是快指针fast=pre.next.next。其中，慢指针指向第一个重复元素，而pre指针，则指向的是第一个不重复的元素，这里就不同于第一章情况，第一种情况因为需要保留一个重复节点，所以重复元素就从pre指针开始，但是第二种情况，对于重复的节点一个都不保留，那么前驱指针pre就得指向第一个不重复得元素，这样的话，利用快指针fast找到最后一个重复元素时，pre指针直接指向最后一个重复元素的next元素，就删除了中间所有的重复元素，没有保留一个。整个过程和第一种情况很相似，代码也极其相似，只是多了一个哨兵节点和指针。其中哨兵节点不存储数据，只是用来简化编码难度，主要是应对头节点出现重复元素的情况，比如上面那个例子。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70 1]

class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            fake = ListNode(None)  #利用哨兵节点简化编码难度
            fake.next = head       #因为如果当头节点元素重复时，不用哨兵节点的话，则需要对头节点特殊处理
            pre = fake
            while pre.next:
                slow = pre.next   #慢指针
                fast = slow.next   #快指针
                if fast:
                    if slow.val == fast.val:
                        while fast:
                            if fast.val != slow.val:
                                break
                            fast = fast.next
                        pre.next = fast
                    else:
                        pre = pre.next
                else:
                    return fake.next
            return fake.next

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200302233418937.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/202003030000214.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI=,size_16,color_FFFFFF,t_70