题解 | 【模板】链表

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        SingLyList list = new SingLyList();
        while (n-- > 0) {
            String str = sc.next();
            if (str.equals("insert")) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                list.insert(x, y);
            } else {
                list.delete(sc.nextInt());
            }
        }
        list.display();
    }
}

class Node {
    int val;
    Node next;

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

    Node(int val) {
        this(val, null);
    }
}

class SingLyList {
    Node head;

    SingLyList() {
        this.head = new Node(-1);
    }

    SingLyList(int val) {
        this();
        this.head.next = new Node(val);
    }

    void insert(int x, int y) {
        Node newNode = new Node(y);
        Node temp = head;
        while (temp.next != null && temp.next.val != x) {
            temp = temp.next;
        }
        // newNode 的下一个指向 temp.next
        newNode.next = temp.next;
        temp.next = newNode;
    }


    void delete(int x) {
        //找到第一个匹配的
        if (head.next == null) {
            return;
        }
        Node temp = head;
        while (temp.next != null && temp.next.val != x) {
            temp = temp.next;
        }
        temp.next = temp.next.next;
    }


    void display() {
          if (head.next == null){
            System.out.println("NULL");
            return;
        }
        Node temp = head.next;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
    }
}

一道数据结构基础的链表题目，勇敢牛牛不怕困难。 和书上的代码相似，构建SingLyList()需要带头节点。插入就是找找到x的位置，要插入到第一个为x的之前。找到x的前一个节点，当new出来的节点指向x，在将之前的节点指向x即可。