83. 删除排序链表中的重复元素

题目

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

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

示例 1：

img

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

img

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

提示：

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

思路

第一种就是使用一个hashmap保存所有的节点的数据，每次遍历的时候要判断当前节点是否有重复

注意：1，1，1的特殊情况

第二种思路：因为链表是升序所以我们可以判断当前链表节点的值和下一个节点的值是否相等，如果相等则重复

实现

第一种：链表升序排列，判断当前链表节点的值和下一个节点的值是否相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode node = head;

        while (node.next != null) {
            if (node.val == node.next.val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }

        return head;
    }
}

第二种：使用hashmap存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static class Solution2 {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode node = head, pre = null;
        HashMap<Integer, Integer> cache = new HashMap<>();

        while (node != null) {
            if (cache.containsKey(node.val)) {
                pre.next = node.next;
            } else {
                cache.put(node.val, node.val);
                pre = node;
            }
            node = node.next;
        }

        return head;
    }
}