跳到主要内容

HJ48. 从单向链表中删除指定值的节点

题目描述​

定义单向链表构造方法：先输入整数 n（节点总数），再输入头节点值，随后输入 n-1 个二元组 (a, b) 表示"在值为 b 的节点后插入值为 a 的节点"。保证节点值不重复。构造链表后，删除给定值节点，输出剩余链表。

输入格式​

一行输入：n（节点总数）、头节点值、n-1 个二元组 (a, b)、最后整数 target（待删除节点值）。 保证每个 b 已存在于链表中，每个 a 之前不存在于链表。

输出格式​

一行输出删除后剩余链表的节点值，每个值后跟一个空格。

示例​

示例 1​

输入：

5 2 3 2 4 3 5 2 1 4 3

输出：

2 5 4 1

说明：

  • n=5，头节点值为 2，要删除 3
  • 插入过程：
    • 3 2：在 2 后插入 3 → [2, 3]
    • 4 3：在 3 后插入 4 → [2, 3, 4]
    • 5 2：在 2 后插入 5 → [2, 5, 3, 4]
    • 1 4：在 4 后插入 1 → [2, 5, 3, 4, 1]
  • 删除 3 → [2, 5, 4, 1]

示例 2​

输入：

6 2 1 2 3 2 5 1 4 5 7 2 2

输出：

7 3 1 5 4

解题思路​

第一步：理解问题本质​

本题需要模拟链表的插入和删除操作。输入格式比较特殊：

  • 前两个数是 n（总节点数）和头节点值
  • 接下来是 n-1 组 (a, b)，表示"在值为 b 的节点后面插入值为 a 的节点"
  • 最后一个数是要删除的节点值

第二步：两种实现方式​

方式一：列表模拟（推荐，代码简洁）

由于题目只要求最终输出，不涉及复杂的链表操作，可以用 Python 列表模拟：

  • list.index(b) 找到 b 的位置
  • list.insert(index+1, a) 在 b 后插入 a
  • list.remove(target) 删除指定值

方式二：真实链表

定义 ListNode 类，实现插入和删除逻辑。更适合面试展示对链表的掌握。

第三步：插入顺序分析​

注意：插入操作是按顺序执行的，后续插入可能插到前面插入的节点后面。

例如 [2, 5, 3, 4] 中，先在 2 后插 3，再在 2 后插 5，最终 5 在 3 前面。

完整代码实现​

列表模拟法（推荐）​

import sys


def solve():
    data = list(map(int, sys.stdin.readline().split()))
    n = data[0]               # 节点总数
    head = data[1]            # 头节点值
    target = data[-1]         # 要删除的节点值

    lst = [head]

    # 从索引 2 开始，每两个一组执行插入
    for i in range(2, 2 * n, 2):
        a = data[i]           # 待插入节点的值
        b = data[i + 1]       # 目标节点的值
        index_b = lst.index(b)
        lst.insert(index_b + 1, a)

    lst.remove(target)

    for val in lst:
        print(val, end=' ')
    print()


if __name__ == "__main__":
    solve()

真实链表法​

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


def solve_linked_list():
    data = list(map(int, sys.stdin.readline().split()))
    n, head_val, target = data[0], data[1], data[-1]

    head = ListNode(head_val)

    for i in range(2, 2 * n, 2):
        a_val, b_val = data[i], data[i + 1]
        cur = head
        while cur and cur.val != b_val:
            cur = cur.next
        if cur:
            new_node = ListNode(a_val)
            new_node.next = cur.next
            cur.next = new_node

    # 删除节点
    if head.val == target:
        head = head.next
    else:
        cur = head
        while cur.next and cur.next.val != target:
            cur = cur.next
        if cur.next:
            cur.next = cur.next.next

    cur = head
    while cur:
        print(cur.val, end=' ')
        cur = cur.next
    print()

示例推演​

以输入 5 2 3 2 4 3 5 2 1 4 3 为例：

步骤 1：初始化列表 [2]

步骤 2：逐组插入

步骤二元组操作列表变化
13, 2在 2 后插 3[2, 3]
24, 3在 3 后插 4[2, 3, 4]
35, 2在 2 后插 5[2, 5, 3, 4]
41, 4在 4 后插 1[2, 5, 3, 4, 1]

步骤 3：删除 3 → [2, 5, 4, 1]

输出：2 5 4 1

复杂度分析​

实现方式时间复杂度空间复杂度说明
列表模拟O(n²)O(n)每次 index 查找 O(n)，共 n 次
真实链表O(n²)O(n)查找节点 O(n)，共 n 次

n 为节点总数

易错点总结​

1. 索引范围错误​

# 错误！范围计算错误
for i in range(2, n * 2 - 1, 2):  # 应该是 2*n，不是 2*n-1

正确范围：range(2, 2 * n, 2)，i 取值 2, 4, 6, ..., 2n-2，共 n-1 组。

2. 插入位置错误​

# 错误！插在 b 前面了
lst.insert(index_b, a)  # 在 b 的位置插入，会把 b 往后推

正确：lst.insert(index_b + 1, a)，在 b 的后面插入。

3. 头节点删除​

链表实现中，如果删除的是头节点，需要特殊处理：

if head.val == target:
    head = head.next

不能直接从 head.next 开始遍历删除。

4. 输出格式​

题目要求每个数后跟一个空格，包括最后一个数：

for val in lst:
    print(val, end=' ')
print()  # 最后换行

扩展思考​

  • 如果允许重复值？ index() 只返回第一个匹配的位置，需要调整逻辑。
  • 如果要求删除所有匹配的节点？ 使用 while target in lst: lst.remove(target)。
  • 如果节点值范围很大？ 可以用字典维护值到节点的映射，将查找优化到 O(1)。

相关题目​

加载评论中...