面试题 02.01. 移除重复节点

题目

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

示例1:
输入:[1, 2, 3, 3, 2, 1]
输出:[1, 2, 3]

示例2:
输入:[1, 1, 1, 1, 2]
输出:[1, 2]

提示:
链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。

进阶:
如果不得使用临时缓冲区,该怎么解决?

题解

public ListNode removeDuplicateNodes(ListNode head) {
    // 打表法
    boolean[] table = new boolean[20001];
    ListNode newHead = new ListNode(0);
    ListNode newNode = newHead;

    while (head != null) {
        if (!table[head.val]) {
            ListNode tmp = new ListNode(head.val);
            newNode.next = tmp;
            newNode = tmp;
            table[head.val] = true;
        }

        head = head.next;
    }

    return newHead.next;
}