力扣刷题日记——L83. 删除排序链表中的重复元素

1. 前言

今天是力扣刷题打卡的第四天，今天带来一道简单题。一开始做了一道中等难度的题，但是很遗憾，没有解出来，但是为了不耽误今天的打卡计划，所以先选一个简单题做了，回头做出来那道题再和大家分享。话不多说进入正题吧。

2. 题目描述

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

示例 1：

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

示例 2：

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

提示：

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

3. 题目分析

这道题非常简单啊，就是将链表中的重复元素删除，唯一能考察的地方只有我们对于链表这个数据结构的理解。链表其实就是一个一个的节点，在物理存储上并不连续，依靠指向下一个元素，和上一个元素的指针形成链条，如果只有单个指向的指针就是单链表，如果同时有指向前一个元素和后一个一个元素的指针，这种链表就叫做双向链表。

这道题给出的链表对象如下所示：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

通过上面的代码我们可以知道，在这个链表中有一个元素 val，表示节点的值，next 则是指向下一个节点的指针。

我的思路是，先用一个 Set 集合去存储遍历过程中的元素，然后遍历的时候去判断是否出现过，如果出现过就删除当前元素，如果没有出现过，就接着往下遍历，下面是我的代码：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode cur = head;
        ListNode last = head;
        while(cur!=null){
            if(set.contains(cur.val)){
                //删除此重复元素
                //父节点指向孙节点
                //删除节点，last节点位置不变
                last.next = cur.next;
            }else{
                //不删除节点，将元素添加进去重容器
                set.add(cur.val);
                last = cur;
            }
            cur = cur.next;
        }
        return head;

    }
}

先创建一个 set
然后记录当前节点 cur 和上一个节点 last
接着开始遍历，遍历的条件为当前节点不为 null，如果为 null，则表示当前节点的最后一个节点是上一个节点，所以遍历直接结束
判断元素是否重复，如果重复，删除节点。删除节点的逻辑是将上一个指针的next指向当前节点的下一个指针，相当于，绕过当前节点直接链接在一起，排除了当前节点，这就是删除链表中的节点的常规操作。
如果不重复就把元素加入到 set 中，然后将当前节点设为 last，因为对于下一个节点来说，当前节点就是它的上一个节点
最后返回这个链表的头节点