算法 1.7.1 删除排序链表中的重复元素【leetcode 8

题目描述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

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

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

数据结构

• 链表、指针

算法思维

• 双指针、遍历

解题要点

• 链表节点的删除操作
• 双指针思想的使用

---

解题思路

一. Comprehend 理解题意

• 可以类比“删除排序数组中的重复元素”，且链表的节点删除更加容易
• “同步变化+相互影响”的两个变量 => 双指针问题 => 创建两个指向链表节点的指针

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

双指针解法

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

解题思路

1. 声明两个指针
2. 遍历链表，比较两个指针指向的节点的值
3. 如果 当前节点值 != 目标节点值，则将两节点相连，删除中间节点
   再将 当前节点 和 目标节点 都后移一位
4. 如果 当前节点值 == 目标节点值，则当前节点后移一位
5. 循环结束时，目标节点必定为尾节点，将其 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 变形与延伸

=== 待续 ===