移除重复节点

LeetCode每日一题，面试题02.01. Remone Duplicate Node LCCI

先看题目描述

大意就是让我们移除链表中的重复节点，并将根节点返回

算法和思路

一开始看到这道题，想到的就是遍历每个节点，遍历过程中记录下节点的值，若出现重复值，就删除节点，然后想到遍历的时间复杂度是 O(n)，想让查询是否出现重复值过程达到 O(1) 时间复杂度，于是想到用哈希表，可用哈希表自带的判断 key 是否存在函数

算法源码

import java.util.HashMap;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head== null) return null;
        HashMap<Integer, Integer> vals = new HashMap();
        ListNode node = head;
        ListNode prevNode = head;
        while (node != null) {
            if (vals.containsKey(node.val)) {
                prevNode.next = node.next;
                node.next = null;
                node = prevNode.next;
            } else {
                vals.put(node.val, 1);
                prevNode = node;
                node = node.next;
            }
        }
        return head;
    }
}