• 时间：2022-05-21
• 题目序号：83
• 难度：简单

问题描述

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

来源：力扣（LeetCode）

示例1

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

示例2

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

提示

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

解题思路

这题比较简单，就不做额外的图片说明了，如果不理解的话可以根据代码配合题目描述中的示例图思考

• 首先，根据题意可知链表中的数据是有序的
• 根据有序，我们可以知道，相同的元素一定是连续的（一个挨一个）
• 因此，需要删除相同元素，我们只需要一层循环，并加一个判断
• 在循环过程中，如果当前结点和next结点值相同，就删除next结点
  cur.val == cur.next.val=>cur.next = cur.next.next

注意：如果传进来的链表本身就是一个空链表，我们需要对其做出判断并处理

代码实现

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null){       // 空链表
            return head;
        }
        ListNode cur = head;
        while(cur.next != null){
            if(cur.val == cur.next.val){        // 重复元素
                cur.next = cur.next.next;       // 删除结点
            }else{
                cur = cur.next;         // 指针后移
            }
        }
        return head;
    }
}

总结

• 本题比较简单，但仍需注意循环条件的临界点问题
• 因为最后需要返回链表头结点，因此在遍历链表时不能直接使用head，而是用cur当作指针进行不断后移
  如果使用head遍历，最后就没有头结点作为返回值了