595，删除排序链表中的重复元素

Original 博哥数据结构和算法 2022-05-19

问题描述

来源：LeetCode第83题

难度：简单

存在一个按升序排列的链表，给你这个链表的头节点head，请你删除所有重复的元素，使每个元素只出现一次。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

使用一个指针解决

这题说了链表中的值是按照升序排列的，既然是排过序的，那么相同的节点肯定是挨着的。我们可以使用一个指针cur，每次都要判断是否和他后面的节点值相同，如果相同就把后面的那个节点给删除，这里就以示例2为例来看个视频

最后再来看下代码

public ListNode deleteDuplicates(ListNode head) {
    //如果但前节点是空，或者是单个节点，直接返回
    if (head == null || head.next == null)
        return head;
    //只用一个指针cur指向当前节点
    ListNode cur = head;
    while (cur.next != null) {
        //如果当前节点的值和下一个节点的值相同，
        //就把下一个节点值给删除
        if (cur.val == cur.next.val) {
            cur.next = cur.next.next;
        } else {
            //否则cur就往后移一步
            cur = cur.next;
        }
    }
    return head;
}

递归方式解决

除了上面使用一个指针以外，我们还可以使用递归的方式来解决。这个需要对链表的逆序访问比较熟悉，关于链表的逆序访问也可以看下1，倒叙打印链表。我们还以示例1为例来画个图看一下（如果看不清，图片可点击放大）

最后再来看下代码

public ListNode deleteDuplicates(ListNode head) {
    //递归的边界条件判断
    if (head == null || head.next == null)
        return head;
    //递归，相当于从后往前遍历
    head.next = deleteDuplicates(head.next);
    //如果当前节点和下一个一样，直接返回下一个节点，否则
    //返回当前节点
    return head.val == head.next.val ? head.next : head;
}