LeetCode 面试题 02.01. 移除重复节点

Categories:

题目描述
思路分析
1. 解法一：哈希去重（推荐）
相似题目

题目描述

✅ 面试题 02.01. 移除重复节点

思路分析

解法一：哈希去重（推荐）

核心思路：

使用哈希集合记录已出现的节点值。

逐个遍历链表，若当前节点值已出现，则跳过该节点。

否则保留节点并加入集合。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表长度。

空间复杂度：O(n)，用于哈希集合。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> seen = new HashSet<>();
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curr = head;

        while (curr != null) {
            if (seen.contains(curr.val)) {
                prev.next = curr.next;
            } else {
                seen.add(curr.val);
                prev = curr;
            }
            curr = curr.next;
        }

        return dummy.next;
    }
}

func removeDuplicateNodes(head *ListNode) *ListNode {
	seen := make(map[int]struct{})
	dummy := &ListNode{Next: head}
	prev := dummy
	curr := head

	for curr != nil {
		if _, ok := seen[curr.Val]; ok {
			prev.Next = curr.Next
		} else {
			seen[curr.Val] = struct{}{}
			prev = curr
		}
		curr = curr.Next
	}

	return dummy.Next
}

相似题目

题目	难度	考察点
83. 删除排序链表中的重复元素	简单	链表
82. 删除排序链表中的重复元素 II	中等	链表
203. 移除链表元素	简单	链表
19. 删除链表的倒数第 N 个结点	中等	双指针
141. 环形链表	简单	快慢指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/11916133