题目描述

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

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

示例2:

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

题解

Set

因为有重复的节点, 首先想到的就是利用集合去做, 创建一个集合, 每遍历到一个节点就检查该节点是否在集合中, 在的话就删除该节点, 否则放入集合中.

public ListNode removeDuplicateNodes(ListNode head) {
    ListNode dum = new ListNode(0);
    dum.next = head;
    ListNode pre = dum;
    ListNode cur = head;
    Set<Integer> set = new HashSet<>();

    while (cur != null) {
        if (!set.contains(cur.val)){
            set.add(cur.val);
            pre = pre.next;
        }else {
            pre.next = cur.next;
        }
        cur = cur.next;
    }

    return dum.next;
}

优化一下:

public ListNode removeDuplicateNodes(ListNode head) {
    Set<Integer> set = new HashSet<>();
    ListNode cur = head;
    while (cur != null && cur.next != null) {
        set.add(cur.val);
        if (set.contains(cur.next.val))
            cur.next = cur.next.next;
        else
            cur = cur.next;
    }
    return head;
}