题解 | #从单向链表中删除指定值的节点#

直接手撸一个链表，借助一个map来统计已经创建过节点的值（题目说了，没有重复值）。但是，感觉题目有点问题。

题目输入的数据对建立的都是连续的链表。比如2->1，2->3，则有2->3->1，相当于新来的是一个插入操作，题目的从节点都是新创建的。但是，可能发生这种2->5，3->4，此时没有形成连续的链表，这时候新关系2->3，此时从节点3(还有其自己的从节点)是已经存在的，那么5和4怎么连接呢？我的代码中的下面这个语句块用于加载/创建从节点，将其替换为只创建的语句块，同样可以ac。

// 加载或者创建
if (map.containsKey(value1)) {
	node1 = map.get(value1);
} else {
	node1 = new Node(value1);
	map.put(value1, node1);
}

// 只创建
node1 = new Node(value1);
map.put(value1, node1);

下面是完整的代码：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int nodeNum = sc.nextInt();
        int headNodeValue = sc.nextInt();
        int[] relation = new int[(nodeNum-1)*2];
        int index = 0;
        for (int i = 1; i < nodeNum; i++) {
            relation[index++] = sc.nextInt();
            relation[index++] = sc.nextInt();
        }
        int delete = sc.nextInt();

        Map<Integer, Node> map = new HashMap<>();  // 记录已经创建的节点(节点值不能重复)
        for (int i = 0; i < relation.length - 1; i+=2) {
            // 从节点
            Node node1 = null;
            int value1 = relation[i];
            if (map.containsKey(value1)) {
                node1 = map.get(value1);
            } else {
                node1 = new Node(value1);
                map.put(value1, node1);
            }
            // 主节点
            Node node2 = null;
            int value2 = relation[i+1];
            if (map.containsKey(value2)) {
                node2 = map.get(value2);
                Node succNode2 = node2.next;  // node2原本的从节点
                // Node succNode1 = node1.next;  // node1原本的从节点（先不考虑，题目没说怎么处理）
                node2.next = node1;
                node1.next = succNode2;
            } else {
                node2 = new Node(value2, node1);  // 新创建的node2无从节点
                map.put(value2, node2);
            }
        }

        Node head = map.get(headNodeValue);
        map.clear();

        while (head.next != null) {
            int value = head.value;
            if (value != delete) {
                System.out.print(value + " ");
            }
            head = head.next;
        }
        if (head.value != delete) {
            System.out.println(head.value);
        }

    }
}

class Node {
    int value;
    Node next;

    public Node(int value) {
        this.value = value;
        this.next = null;
    }

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}