题目主要信息

1、输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。

2、链表的值不能重复。

方法一：直接法

具体方法

遍历数组，依次完成节点的插入，在遍历新的一组数据时，先找到前节点，然后将后节点插入到后面。举例说明 6 2 1 2 3 2 5 1 4 5 7 2 2

Java代码

package nowcode;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class HJ8 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str = bf.readLine()) != null) {
            if (str.equals("")) continue;
            String[] split = str.split(" ");
            //总共有多少个节点
            int n = Integer.parseInt(split[0]);
            //头结点
            ListNode head = new ListNode(Integer.parseInt(split[1]));
            for (int i = 1; i < n; i++) {
                int pre = Integer.parseInt(split[2*i+1]), next = Integer.parseInt(split[2*i]);
                //临时遍历链表
                ListNode temp = head;
                //找到插入的位置
                while (temp.val != pre)
                    temp = temp.next;
                ListNode node = new ListNode(next);
                node.next = temp.next;
                temp.next = node;
            }
            int del_number = Integer.parseInt(split[2*n]);
            StringBuilder result = new StringBuilder();
            ListNode temp = head;
            while (temp != null) {
                if (temp.val != del_number)
                    result.append(temp.val).append(" ");
                temp = temp.next;//删除
            }
            // 注意要求每个数后面都加空格
            System.out.println(result.toString());
        }
    }
}
class ListNode {
    ListNode next;
    int val;
    ListNode(int val) {
        this.val = val;
        next = null;
    }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，在遍历数组的时候需要遍历链表。
• 空间复杂度：$O(n)O(n)$，存链表的长度。

方法二：借助ArrayList

具体方法

比如两个数字A B，需要将A插入到B的后面，可以使用linkedlist.indexOf(pre)，找到B所在的位置，在其后面一个位置放入A即可。

linkedlist.add(linkedlist.indexOf(B) + 1, A);

最后删除的时候通过linkedlist.remove(linkedlist.indexOf(remove));即可删除。

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int head = sc.nextInt();
             
            List<Integer> linkedlist = new ArrayList<>();
             
            linkedlist.add(head);
            for (int i = 0; i < n - 1; i ++) {
                int next = sc.nextInt();
                int pre = sc.nextInt();
                linkedlist.add(linkedlist.indexOf(pre) + 1, next);
            }
             
            int remove = sc.nextInt();
            linkedlist.remove(linkedlist.indexOf(remove));
            for (int i : linkedlist) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，LinkedList内部也需要遍历一次找到位置。
• 空间复杂度：$O(n)O(n)$，一个临时的ArrayList的长度。