题目描述
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
数据结构
- 链表、指针
算法思维
- 双指针、遍历
解题要点
- 链表节点的删除操作
- 双指针思想的使用
解题思路
一. Comprehend 理解题意
- 可以类比“删除排序数组中的重复元素”，且链表的节点删除更加容易
- “同步变化+相互影响”的两个变量 => 双指针问题 => 创建两个指向链表节点的指针
二. Choose 选择数据结构与算法
双指针解法
- 数据结构：指针
- 算法思维：双指针、遍历
解题思路
- 声明两个指针
- 遍历链表，比较两个指针指向的节点的值
- 如果 当前节点值 != 目标节点值，则将两节点相连，删除中间节点
再将 当前节点 和 目标节点 都后移一位 - 如果 当前节点值 == 目标节点值，则当前节点后移一位
- 循环结束时，目标节点必定为尾节点，将其 next 设置为 null
边界问题
- 当前指针（curr）永远领先于目标指针（target），边界：
curr == null
细节问题
- 需要进行非空判断，避免
curr = head.next出现空指针异常 - 遍历结束时，target 必定为尾节点，需将其 next 设置为 null，丢掉 target 后连接的多余节点
三. Code 编码实现基本解法
class Solution {
public ListNode deleteDuplicates(ListNode head) {
//0.非空判断
if (head == null) return null;
//1.声明两个指针
ListNode target = head;
ListNode curr = head.next;
//2.遍历链表，比较两个指针指向的节点的值
while(curr != null){
//3.如果当前值 != 目标值，连接两节点（删除中间节点），目标节点后移一位
if (curr.val != target.val){
target.next = curr;
target = curr;
}
//4.无论 当前值 是都等于 目标值，当前节点都要后移一位
curr = curr.next;
}
//5.循环结束时，target 必定为尾节点，将其 next 设置为 null
target.next = null;
return head;
}
}
执行耗时：0 ms，击败了 100.00% 的Java用户
内存消耗：37.9 MB，击败了 61.39% 的Java用户
时间复杂度：O(n) -- 链表的遍历 O(n)
空间复杂度：O(1) -- 两个指向链表节点的指针的内存空间 O(1)
四. Consider 思考更优解
优化代码结构
改变算法思维
借鉴其他算法
五. Code 编码实现最优解
执行耗时：
内存消耗：
时间复杂度：O() --
空间复杂度：O() --
六. Change 变形与延伸
=== 待续 ===
