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

这道题要想做对第一步要理解题意

题意的意思是说刨除去前面两个数，从第三个数起，两两为一组来构建列表，构建的方式是每一组的第二个数是原链表的数，第一个数是要插入的数，要插入的数的位置就是第二个数所在链表位置的后面。由于这道题告诉我们不会有重复的数字，所以不会造成不知道该插入哪个位置的情况。所以构建链表的过程一定要按照题意。我刚刚开始就想当然自己常规构建，结果那就是一个错误百出。

接下来就两件事儿，

1、从链表当中删除某个数字

这也不能大意，你一大意跟我似的，忘了写链表指针移动那一行，那就是个死循环，多酸爽。

2、打印链表，由于我们已经构建了链表，打印就易如反掌了。也要注意打印的顺序。你打印反了，机器考试的时候也会一脸懵啊，

时间复杂度是O(n)

空间复杂度O(n)

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String ss = in.nextLine();
        String[] sss = ss.split(" ");
        int n = Integer.parseInt(sss[0]);
        int toDelete = Integer.parseInt(sss[sss.length - 1]);
        Node prev = new Main.Node();
        buildChain(prev, sss);
        deleteOne(prev, toDelete);
        print(prev.next);


    }

         private static void print(Main.Node prev) {
        // TODO
      
        while (prev!=null){
            System.out.print(prev.data);
            System.out.print(" ");
            prev=prev.next;
        }

    }

    private static void deleteOne(Main.Node prev, int toDelete) {
        Main.Node temp = prev;
        while (temp.next != null) {
            if (temp.next.data == toDelete) {
                temp.next = temp.next.next;
            }
            //易错点：需要移动步伐，不要忘了！！！！
            temp = temp.next;
        }
    }

    private static void buildChain(Main.Node prev, String[] sss) {
        int start = Integer.parseInt(sss[1]);
        Node one = new Node();
        one.data = start;
        prev.next = one;
        Set<Integer> set = new HashSet<>();
        set.add(one.data);

        for (int i = 2; i < sss.length - 1; i += 2) {
            if (!set.contains(sss[i])) {
                link(prev, sss[i], sss[i + 1]);
                set.add(Integer.parseInt(sss[i]));

            }
        }

    }

    private static void link(Node prev, String toInsert, String hasInsert) {
        Node temp = prev;
        while (temp.next != null) {
            if (temp.next.data == Integer.parseInt(hasInsert)) {
                Node node = new Node();
                node.data = Integer.parseInt(toInsert);
                Node secondLink = temp.next.next;
                temp.next.next = node;
                if (secondLink != null) {
                    node.next = secondLink;
                }
                break;
            }
            temp = temp.next;
        }
    }

    private static Node buildChain(Main.Node prev, String[] sss, int index) {

        if (index < (sss.length - 2)) {
            Node priv = buildChain(prev, sss, index + 1);
            Node temp = new Node();
            temp.data = Integer.parseInt( sss[index]);
            priv.next = temp;
            return temp;
        } else {
            Node temp = new Node();
            temp.data = Integer.parseInt( sss[index]);
            prev.next = temp;
            return prev.next;
        }
    }

    public  static class Node {
        public int data;
        public  Node next;
        public  void Node() {};

    }
}