算法 1.7.2 删除排序链表中的重复元素 II【leetcod

题目描述

2/4
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字

示例 1:
  输入: 1->2->3->3->4->4->5
  输出: 1->2->5

示例 2:
  输入: 1->1->1->2->3
  输出: 2->3

数据结构

• 链表、指针

算法思维

• 遍历、双指针 + 状态机

解题要点

• 熟练掌握双指针解题思路和使用方法
• 使用状态机 在不同情况下 控制指针的移动策略

---

解题思路

一. Comprehend 理解题意

• “删除排序链表中的重复元素” 的进阶版
• 不再保留重复元素的其中一个，重复元素全部删除
• 不能直接判断 target 和 curr 的值是否相等，而是判断 target.next 和 curr 的值

二. Choose 选择数据结构与算法

双指针解法

• 数据结构：指针
• 算法思维：遍历、双指针 + 状态机

解题思路

1. 声明一个新的头节点，两个指针变量，一个状态机（布尔量）
     新头节点（newHead）指向原头节点
     目标指针（target）指向新头节点
     当前指针（curr）指向原头节点的下一个节点
     状态机（hasRepeat）记录当前 target 与 curr 之间是都有重复节点
2. 遍历整个链表
3. 不断判断 curr.val 是否等于 target.next.val
     如果相等，将状态机置为 true
     如果不相等，判断状态机状态
       如果状态为 true 说明 curr 前为重复节点，删除重复节点，还原状态机为 false
       如果状态为 false 说明 curr 前无重复节点，目标节点 target 后移
4. 不管任何情况，curr 都照常后移
5. 最终需要判断 target 后的节点是否为重复的，若为重复节点则删除

边界问题

• 当前指针（curr）至少领先目标指针（target）两个节点，边界：curr == null

细节问题

• 需要进行非空判断，避免 curr = head.next 出现空指针异常
• 需要定义一个新的头节点指针，指向原头节点，用于最终返回（因为原头节点可能会因为重复而被删掉）
    注意：返回时要返回 return newHead.next
• 在遍历结束（curr == null）之前的一步，存在两种情况：
    1）target.next.val == curr.val 此时 target 指针后均为重复节点，target 即为尾节点
      需设置 target.next = null，丢掉 target 后的重复节点（注意：此时 boolean 为 true）
    2）target.next.val != curr.val 此时不管 target 和 curr 之间是否有重复节点，target.next 最终都会指向 curr
      即最终 target.next 为尾节点，链表结尾没有重复节点（注意：此时 boolean 为 false）

三. Code 编码实现基本解法

class Solution {
    public ListNode deleteDuplicates(ListNode head) {

        //0.非空判断
        if (head == null) return null;

        //1.声明一个新头节点，两个指针变量，一个状态机（布尔量）
        ListNode newHead = new ListNode(-1, head); //新头节点指向原头节点
        ListNode target = newHead; //目标指针指向新头节点
        ListNode curr = head.next; //当前指针指向原头节点的下一个节点
        boolean hasRepeat = false; //记录当前 target 与 curr 之间是都有重复节点

        //2.遍历整个链表
        while (curr != null) {
            //3.不断判断当前指针节点值 是否等于 目标指针下一个节点的节点值
            if (target.next.val == curr.val) {
                //4.如果相等，将状态机置为 true
                hasRepeat = true;
            } else if (hasRepeat) { //5.如果不相等，判断状态机状态
                //6.如果状态为 true 说明 curr 前为重复节点，删除重复节点
                target.next = curr;
                hasRepeat = false; //还原状态机为 false
            } else {
                //7.如果状态为 false 说明 curr 前无重复节点，目标节点 target 后移
                target = target.next;
            }

            //8.不管任何情况，curr 都照常后移
            curr = curr.next;
        }

        //9.最终需要判断 target 后的节点是否为重复的，若为重复节点则删除
        if (hasRepeat) target.next = null;

        return newHead.next;
    }
}

执行耗时：0 ms，击败了 100.00% 的Java用户
内存消耗：37.9 MB，击败了 48.39% 的Java用户
时间复杂度：O(n) -- 链表的遍历 O(n)
空间复杂度：O(1) -- 一个新节点 O(1)，两个指针的内存空间 O(1)，一个布尔值的内存空间 O(1)

四. Consider 思考更优解

改变算法思维

• 使用双层循环结构代替状态机控制指针移动

五. Code 编码实现最优解

class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        if(head==null || head.next==null) {
            return head;
        }

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode a = dummy;
        ListNode b = head;

        while(b!=null && b.next!=null) {
            //初始化的时a指向的是哑结点，所以比较逻辑应该是a的下一个节点和b的下一个节点
            if(a.next.val!=b.next.val) {
                a = a.next;
                b = b.next;
            } else {
                //如果a、b指向的节点值相等，就不断移动b，直到a、b指向的值不相等 
                while(b!=null && b.next!=null && a.next.val==b.next.val) {
                    b = b.next;
                }
                a.next = b.next;
                b = b.next;
            }
        }

        return dummy.next;
    }

}

执行耗时：1 ms，击败了 65.62% 的Java用户
内存消耗：37.8 MB，击败了 73.67% 的Java用户
时间复杂度：O(n) -- 一次链表遍历 O(n)
空间复杂度：O(1) -- 一个新节点 O(1)，两个指针的内存空间 O(1) ，一个布尔值的内存空间 O(1)

六. Change 变形与延伸

=== 待续 ===