2015 年第 41 题

题目描述

设线性表 (a1, a2, a3, ..., an) 中的元素递增有序且按单链表存储。要求删除链表中绝对值相等的多余结点，只保留第一次出现的结点。

例如：

1 -> 2 -> -2 -> 3 -> -3 -> 4

处理后：
1 -> 2 -> 3 -> 4

解题思路

因为判断重复的标准是“绝对值是否出现过”，所以可以开一个辅助数组或哈希集合 seen_abs：

1. 从前往后扫描链表。
2. 若当前结点绝对值没出现过，则标记为已出现，继续向后。
3. 若已经出现过，则删除当前结点。

由于题目强调单链表删除，所以实现时要一直维护前驱指针 pre。

手算示例

链表：1 -> 2 -> -2 -> 3 -> -3 -> 4

seen = {}

读到 1，|1| 未出现，保留
seen = {1}

读到 2，|2| 未出现，保留
seen = {1, 2}

读到 -2，| -2 | = 2 已出现，删除 -2

读到 3，|3| 未出现，保留
seen = {1, 2, 3}

读到 -3，| -3 | = 3 已出现，删除 -3

读到 4，|4| 未出现，保留

Python 实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def remove_duplicate_abs(head: ListNode):
    """
    head 为带表头结点的单链表
    """
    seen = set()
    pre = head
    cur = head.next

    while cur is not None:
        key = abs(cur.val)
        if key in seen:
            pre.next = cur.next
        else:
            seen.add(key)
            pre = cur
        cur = cur.next

    return head

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

易错点

• 判重依据是绝对值，不是元素本身。
• 删除单链表结点时必须保留前驱指针。
• 删除结点后，pre 不应后移。

对应题

来源	题目	相似度	主要差异
程序员面试金典	02.01. 移除重复节点	90%	真题按绝对值去重
LeetCode	203. 移除链表元素	70%	该题是按指定值删除，不是去重

难度

⭐️⭐️