首页 > 试题广场 >

在链表中删除指定值的节点

[编程题]在链表中删除指定值的节点

热度指数：1904 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个链表和一个整数 num，输出删除链表中节点值等于 num 的节点之后的链表。

输入描述:

第一行一个整数 n，n 表示单链表的节点数量。

第二行 n 个整数表示单链表的各个节点的值。

第三行一个整数 num。

输出描述:

在给定的函数中返回指定链表的头指针。

示例1

输入

4 
1 2 3 4
3

输出

1 2 4

备注:

算法知识视频讲解

C/C++

nbgao

list_node * remove_value(list_node * head, int num)
{
    list_node *pre=NULL, *cur=head;
    while(cur != NULL){
        if(cur->val == num)
            pre->next = cur->next;
        pre = cur;
        cur = cur->next;
    }
    return head;
}

发表于 2020-05-18 07:45:22 回复(0)

C++

牛客66319561号

C++,可以运行。

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};

list_node * input_list()
{
    int val, n;
    scanf("%d", &n);
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}


list_node * remove_value(list_node * head, int num)
{
    //////在下面完成代码
    while(head->val==num) head=head->next;
    list_node* pre=head;
    list_node* cur=head->next;
    while(cur!=NULL){
        if(cur->val==num) {
            pre->next=cur->next;
            cur=pre->next;
        }else{
            pre=pre->next;
            cur=cur->next;
        }
    }
    return head;
}

void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main ()
{
    list_node * head = input_list();
    int num;
    scanf("%d", &num);
    list_node * new_head = remove_value(head, num);
    print_list(new_head);
    return 0;
}

发表于 2021-07-23 10:43:18 回复(0)

Python

毓毓子最可爱

n=int(input())
number_list=list(map(int,input().split()))
m=int(input())
#如果还存在要删除的数字
#一直删除
while m in number_list:
    number_list.remove(m)
print(" ".join(map(str,number_list)))

发表于 2021-06-30 09:50:14 回复(0)

p_string

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] rawInput = br.readLine().trim().split(" ");
        int num = Integer.parseInt(br.readLine().trim());
        
        Node head = buildLinkedList(rawInput);
        
        head = delNode(head, num);
        
        printLinkedList(head);
        
        br.close();
    }
    
    private static Node delNode(Node head, int num) {
        if (null == head) {
            return null;
        }
        
        Node curNode = head, preNode = null;
        while (null != curNode) {
            if (curNode.value == num) {
                // 换头
                if (curNode == head) {
                    head = head.next;
                } else {
                    preNode.next = curNode.next;
                }
            } else {
                preNode = curNode;
            }
            curNode = curNode.next;
        }
        
        return head;
    }
    
    private static Node buildLinkedList(String[] rawInput) {
        Node head = null, curNode = null;
        
        for (int i = 0; i < rawInput.length; i++) {
            Node tmpNode = new Node(Integer.parseInt(rawInput[i]));
            if (null == head) {
                head = tmpNode;
            } else {
                curNode.next = tmpNode;
            }
            curNode = tmpNode;
        }
        
        return head;
    }
    
    private static void printLinkedList(Node head) {
        if (null == head) {
            return;
        }
        StringBuilder sb = new StringBuilder();
        while (null != head) {
            sb.append(head.value).append(" ");
            head = head.next;
        }
        System.out.print(sb.toString().trim());
    }
}

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

发表于 2020-08-05 09:43:58 回复(0)

北冥i鱼

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
    int data;
    struct LNode* next;
}LNode,*LinkList;

LinkList Init();
void GetNum(LinkList H,int n);
void Del(LinkList H,int e);
int main()
{
    LinkList H,q;
    int n,e;
    H = Init();
    scanf("%d",&n);
    GetNum(H,n);
    scanf("%d",&e);
    Del(H,e);
    q = H->next;
    while(q){
        printf("%d ",q->data);
        q = q->next;
    }
    system("pause");
}
LinkList Init()
{
    LinkList H = malloc(sizeof(LNode));
    H->next = NULL;
    return H;
}
void GetNum(LinkList H,int n)
{
    LinkList p = H,q;
    int e;
    for(int i = 0; i < n; i++){
        scanf("%d",&e);
        q = (LinkList)malloc(sizeof(LNode));
        q->data = e;
        q->next = NULL;
        p->next = q;
        p = q;
    }
}
void Del(LinkList H,int e)
{
    LinkList p = H,q;
    while(p->next){
        if(p->next->data == e){
            q = p->next;
            p->next = q->next;
            free(q);
        }
        p = p->next;
    }
}

编辑于 2020-04-13 18:04:57 回复(0)

我笨蛋啊

基本思路：
1、首先将所有节点值存在数组中，然后再根据循环放入链表
2、删除链表方法
3、打印

class ListNode{
    int val;
    ListNode next;
    ListNode(int val){
        this.val=val;
    }
}

public class Main{

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        ListNode head=new ListNode(a[0]);
        ListNode cur=head;
        for(int i=1;i<n;i++){
            cur.next=new ListNode(a[i]);
            cur=cur.next;
        }
        cur.next=null;
        int val=sc.nextInt();
        ListNode node=removeElements(head,val);
        printList(node);
    }
    public static void printList(ListNode head){
        while(head!=null){
            System.out.print(head.val+" ");
            head=head.next;
        }
    }
    public static ListNode removeElements(ListNode head,int val){
        if(head==null){
            return head;
        }
        ListNode cur=head;
        ListNode res=null;
        while(cur!=null){
            if(cur.val==val){
                if(cur==head){
                    head=head.next;
                }else{
                    res.next=cur.next;
                }
            }else{
                res=cur;
            }
            cur=cur.next;
        }
        return head;
    }
}

发表于 2020-03-01 00:55:31 回复(0)

EVANnnn1996

注意头结点的值就是 num 的情况。

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

public class Main {
    
    public static class Node {

        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    
    public static Node listGenerator(int length, String[] numbers) {
        Node head = new Node(Integer.parseInt(numbers[0]));
        Node cur = head;
        for (int i = 1; i < length; i++) {
            cur.next = new Node(Integer.parseInt(numbers[i]));
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.value +" ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static Node removeValue(Node head, int num) {
        while (head != null) {
            if (head.value != num) {
                break;
            }
            head = head.next;
        }
        Node pre = head;
        Node cur = head;
        while (cur != null) {
            if (cur.value == num) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = pre.next;
        }
        return head;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        String[] numbers = bufferedReader.readLine().split(" ");
        int num = Integer.parseInt(bufferedReader.readLine());
        Node head = listGenerator(n, numbers);
        Node newHead = removeValue(head, num);
        printList(newHead);
    }
}

发表于 2020-02-13 21:11:17 回复(0)

小妹妹的超仔

#include <stdio.h>
#include <stdlib.h>
typedef struct LinkedList{
    int data;
    struct LinkedList *next;
}Node;

void output(Node *L)//遍历
{
   Node *p;
   for (p = L->next; p != NULL; p = p->next)
   {
       printf("%d ", p->data);
   }
}

Node *CreateLinkedListTail(int n)
{
    int x;
    Node *L;
    L = (Node*)malloc(sizeof(Node));
    L->next = NULL;
    Node *now;
    now = (Node*)malloc(sizeof(Node));
    now = L;
    for(int i=0;i<n;i++){
        Node *p;
        p =(Node*)malloc(sizeof(Node));
        scanf("%d",&x);
        p->data = x;
        now->next = p;
        now = p;
    }
    now->next = NULL;
    return L;
}

void Sort(Node *L,int n)
{
    Node *p,*q;

   p = (Node*)malloc(sizeof(Node));
    p=L->next;
    q = (Node*)malloc(sizeof(Node));
   q=L;
   while(p->data != n){
       q = q->next;
       p = p->next;
   }
   if(p->data == n)
   {
       q->next = p->next;
   }
   free(p);
}
int main(int argc,char **argv)
{
    int len,n;
    Node *L;
    scanf("%d",&len);
    L = CreateLinkedListTail(len);
   scanf("%d",&n);
    Sort(L,n);
    output(L);
    return 0;
}

发表于 2019-11-28 10:20:51 回复(0)

spicychicken123

list_node * remove_value(list_node * head, int num)
{
    //////在下面完成代码
    struct list_node *pre,*cur;
    while(head!=NULL&&head->val==num){
        head=head->next;
        free(cur);
        cur=head;
    }
    pre=head;
    cur=pre->next;
    while(cur){
        if(cur->val==num){
            pre->next=cur->next;
            free(cur);
            cur=cur->next;
        }else{
            pre=cur;
            cur=cur->next;
        }
    }
    return head;
}

发表于 2019-09-21 16:27:58 回复(0)