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

从单向链表中删除指定值的节点

http://www.nowcoder.com/practice/f96cd47e812842269058d483a11ced4f

题目主要信息

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

2、链表的值不能重复。

方法一:直接法

具体方法

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

alt

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(n2)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(n2)O(n^2),LinkedList内部也需要遍历一次找到位置。
  • 空间复杂度:O(n)O(n),一个临时的ArrayList的长度。
华为机试 文章被收录于专栏

本专栏主要用于分享华为机试的题解,希望对大家有所帮助。

全部评论
厉害!
点赞 回复 分享
发布于 2024-01-05 13:54 新疆
谢谢,终于明白题干在说什么了……
点赞 回复 分享
发布于 2023-08-07 21:55 广东

相关推荐

09-08 17:17
同济大学 Java
狗不理fe:里面的人劝一句,别来虾,我们部门24校招生淘汰率30%,还有一些人说有一年保护期,不可能!!!
我的秋招日记
点赞 评论 收藏
分享
牛客83265014...:完了,连现在都没开始面,13号投的是不是晚了
秋招的第一个offer,...
点赞 评论 收藏
分享
评论
21
11
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务