题目描述
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 选择数据结构与算法
双指针解法
- 数据结构：指针
- 算法思维：遍历、双指针 + 状态机
解题思路
- 声明一个新的头节点，两个指针变量，一个状态机（布尔量）
新头节点（newHead）指向原头节点
目标指针（target）指向新头节点
当前指针（curr）指向原头节点的下一个节点
状态机（hasRepeat）记录当前 target 与 curr 之间是都有重复节点 - 遍历整个链表
- 不断判断
curr.val是否等于target.next.val
如果相等，将状态机置为 true
如果不相等，判断状态机状态
如果状态为 true 说明 curr 前为重复节点，删除重复节点，还原状态机为 false
如果状态为 false 说明 curr 前无重复节点，目标节点 target 后移 - 不管任何情况，curr 都照常后移
- 最终需要判断 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 变形与延伸
=== 待续 ===
