首页 > 试题广场 >

一种怪异的节点删除方式

[编程题]一种怪异的节点删除方式

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

链表节点值类型为 int 类型，给定一个链表中的节点 node，但不给定整个链表的头节点。如何在链表中删除 node ? 请实现这个函数。

输入描述:

给出一个单链表的节点。

输出描述:

不需要返回值。

示例1

输入

5 
1 2 3 4 5
3

输出

1 2 4 5

备注:

保证要删除的这个节点不是链表的尾节点。

算法知识视频讲解

柠檬茶c

void remove_node_wired(list_node * node)
{
    //////在下面完成代码
    if (node -> next != NULL) {
        node -> val = node -> next -> val;
        list_node *temp = node -> next;
        node -> next = node -> next -> next;
        free(temp);
    } else {
        free(node);
    }
}

发表于 2020-08-06 10:49:19 回复(0)

C/C++

nbgao

void remove_node_wired(list_node * node)
{
    while(node->next){
        node->val = node->next->val;
        if(node->next->next == NULL){
            node->next = NULL;
            return;
        }
        node = node->next;
    }
}

发表于 2020-06-11 02:04:28 回复(0)

C/C++

lvjingxiao

void remove_node_wired(list_node * node)
{
    //因为无法获取前驱，将后继的值赋给当前节点，删除后继结点
    //如果是尾节点
    if(node->next==NULL)
        return;
    //中间节点
    else{
        node->val=node->next->val;
        node->next=node->next->next;
    }
}

发表于 2020-01-01 14:44:29 回复(0)

pein531

当前节点的值改为后一个节点的值，然后把后一个节点跳过（我成为你，然后再干掉你，就相当于我干掉了我自己）。

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

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

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());
        String[] elements = br.readLine().trim().split(" ");
        int target = Integer.parseInt(br.readLine());
        ListNode head = new ListNode(Integer.parseInt(elements[0]));
        ListNode cur = head;
        ListNode targetNode = target == 0? head: null;
        for(int i = 1; i < n; i++){
            cur.next = new ListNode(Integer.parseInt(elements[i]));
            cur = cur.next;
            if(i + 1 == target) targetNode = cur;
        }
        deleteNode(targetNode);
        while(head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    
    private static void deleteNode(ListNode targetNode){
        if(targetNode == null) return;
        targetNode.val = targetNode.next.val;
        targetNode.next = targetNode.next.next;
    }
}

发表于 2021-06-02 09:35:12 回复(0)

想写cpp的大橘子

这种链表的和树的题目麻烦死了

构造过程的复杂度大于解决问题的复杂度。

建议搞一个填函数模式。

发表于 2023-09-27 11:51:43 回复(0)

C++

牛客66319561号

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

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

list_node * find_kth_node(list_node * head, int k)
{
    list_node * c = head;
    for (int i = 1; i < k; ++i) c = c->next;
    return c;
}

list_node * input_list(void)
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d", &n);
    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;
}


void remove_node_wired(list_node * node)
{
    //////在下面完成代码
    /*
    将当前节点的值更换为下一个节点的值，然后删除下一个节点
    */
    list_node* cur=node->next;
    node->val=cur->val;
    node->next=cur->next;
}


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 n;
    scanf("%d", &n);
    list_node * node = find_kth_node(head, n);
    remove_node_wired(node);
    print_list(head);
    return 0;
}

编辑于 2021-07-24 09:53:13 回复(0)

Python

毓毓子最可爱

n=int(input())
linked_list=input().split()
node=int(input())
linked_list.pop(node-1)
print(' '.join(linked_list))

题有问题，把node当做列表中的元素进行删除时一直报错，当做下标时是正确的。

python list中pop()这个函数的参数是元素的索引，删除索引上的那个元素

list中remove()这个函数的参数是元素值，直接删除那个元素

编辑于 2021-06-11 08:38:52 回复(0)

牛客760003581号

1找到node的下一个节点，next=node.next2,node.val=next.valnode.next = next.next

发表于 2021-01-16 17:32:27 回复(0)

H.T.W

acm模式就是指一切都要自己构造么？

发表于 2021-01-14 17:48:51 回复(0)

程序猿的浪漫

为啥评论区人这么少，把代码贴出来互相学习学习

void remove_node_wired(list_node * node){
    //////在下面完成代码
    if(node->next == nullptr){
        delete node;
        node = nullptr;
        return;
    }
    node->val = node->next->val;
    node->next = node->next->next;
}

发表于 2020-07-08 20:32:11 回复(0)

王仙客船长

void remove_node_wired(list_node * node)
{
    //////在下面完成代码
    if (!node) return;
    if (!node->next) {
        node = NULL;
        return;
    }
    int val = node->next->val;
    node->val = val;
    node->next = node->next->next;
}

发表于 2020-06-13 23:53:06 回复(0)

chichichi66

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 void remove(Node node) { if (node == null) { return; } else if (node.next == null) { throw new RuntimeException("cannot remove last node!"); } else { node.value = node.next.value; node.next = node.next.next; } } 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 node = head; int index = 1; while (node != null && index != num) { node = node.next; index++; } remove(node); printList(head); } }

发表于 2020-02-18 21:06:58 回复(0)

EVANnnn1996

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 void remove(Node node) {
        if (node == null) {
            return;
        } else if (node.next == null) {
            throw new RuntimeException("cannot remove last node!");
        } else {
            node.value = node.next.value;
            node.next = node.next.next;
        }
    }

    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 node = head;
        int index = 1;
        while (node != null && index != num) {
            node = node.next;
            index++;
        }
        remove(node);
        printList(head);
    }
}

发表于 2020-02-15 10:46:41 回复(0)