Java 第80题：单链表：删除值为 x 的节点

题目

在单链表中查找并删除第一个节点值等于目标值 x 的节点，输出删除后的新链表内容。

输入格式：第一行输入节点数量 n；第二行输入 n 个整数建立链表；第三行输入待删除的值 x。

输出格式：输出删除目标节点后的完整链表，每个数字后跟空格，末尾换行。

数据范围与约定：1 ≤ n ≤ 100。

思路与算法

1. 头节点删除特判
若被删节点正好是头节点 head->val == x，直接将 head 更新为 head->next，并 垃圾回收 GC 原头节点。

2. 中间/尾部节点删除
维护前驱指针 prev 和当前指针 cur。命中后执行 prev->next = cur->next; 垃圾回收 GC(cur); 完成跨节点断开与空间回收。

完整程序

import java.util.Scanner;

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n <= 0) return;

        // 尾插法建表以保持原始输入顺序
        ListNode head = new ListNode(sc.nextInt());
        ListNode tail = head;
        for (int i = 1; i < n; i++) {
            tail.next = new ListNode(sc.nextInt());
            tail = tail.next;
        }

        int x = sc.nextInt();

        // 删除第一个值为 x 的节点
        if (head.val == x) {
            head = head.next;
        } else {
            ListNode prev = head;
            while (prev.next != null) {
                if (prev.next.val == x) {
                    prev.next = prev.next.next;
                    break;
                }
                prev = prev.next;
            }
        }

        // 输出剩余链表
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + (cur.next != null ? " " : "\n"));
            cur = cur.next;
        }
    }
}

运行示例

输入：

4
1 2 3 2
2

输出：

1 3 2