首页 > 试题广场 >

删除链表的中间节点

[编程题]删除链表的中间节点
  • 热度指数：2263 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个链表，实现删除链表第 K 个节点的函数。

输入描述:
n 表示链表的长度。

m 表示删除链表第几个节点。

val 表示链表节点的值。


输出描述:
在给定的函数中返回链表的头指针。
示例1

输入

5 3
1 2 3 4 5

输出

1 2 4 5

备注:


算法知识视频讲解
添加回答
offer之神降临吧头像 offer之神降临吧 
list_node * remove_kth_node(list_node * head, int K)
{
    //////在下面完成代码
    list_node * temp = head;
    for(int i = 1; i < K-1;i++){
        if(!temp)
            return head;
        temp = temp->next;
    }
    temp->next = temp->next->next;
    return head;
}

发表于 2020-05-10 11:45:05 回复(0)
C
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct ListNode {
  ElemType data;
  struct ListNode* next;
} ListNode, *PLNode, *L;

void print_list(L head) {
  while (head) {
    fprintf(stdout, "%d", head->data);
    if (head->next) fputc(32, stdout);
    head = head->next;
  }
}

int main(const int argc, const char* const argv[]) {
  int n, m;
  fscanf(stdin, "%d %d", &n, &m);
  
  L dummy = (PLNode) malloc (sizeof(ListNode));
  if (!dummy) exit(0);
  
  int x;
  PLNode tail = dummy;
  while (fscanf(stdin, "%d", &x) != EOF) {
    tail = tail->next = (PLNode) malloc(sizeof(ListNode));
    tail->data = x;
    tail->next = NULL;
  }
  
  PLNode pre, curr = dummy;
  while (m--) {
    pre = curr;
    curr = curr->next;
  }
  pre->next = curr->next; // delete node
  
  print_list(dummy->next);
  return 0;
}

发表于 2021-08-04 11:01:43 回复(0)
pein531头像 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));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        String[] elements = br.readLine().trim().split(" ");
        int target = Integer.parseInt(params[1]);
        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:34:23 回复(0)
C/C++
nbgao头像 nbgao 
# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
}; //链表的节点

int K;

list_node * input_list(void) //读入链表
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d %d", &n, &K);
    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_kth_node(list_node * head, int K)
{
    list_node * rhead = new list_node();
    rhead->next = head;
    list_node * pre = rhead;
    list_node * cur = head;
    while(cur != NULL){
        if(--K == 0)
            pre->next = cur->next;
        pre = cur;
        cur = cur->next;
    }
    return rhead->next;
}

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

int main ()
{
    list_node * head = input_list(); // 链表的头节点
    list_node * rhead = remove_kth_node(head, K);
    print_list(rhead);
    return 0;
}

发表于 2020-04-27 01:04:41 回复(0)
唉梅子头像 唉梅子 
list_node * remove_kth_node(list_node * head, int K)
{
    //////在下面完成代码
    list_node * node = new list_node;
    if(K == 1){
        node->next = head->next;
        return node->next;
    }
    node->next = head;
    list_node *p = head;
    for(int i = 0;i < K-2;i++){
        p = p->next;
    }
    if(p->next->next){
        p->next = p->next->next;
    }
    else{
        p->next = nullptr;
    }
    return node->next;
}

发表于 2019-08-02 19:32:13 回复(0)
C
helloxuanbao头像 helloxuanbao 
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int val;
    struct node *next;
} Node;

Node *newNode(int val);

void freeList(Node *head);

Node *removeKthNode(Node *head, int k);

int main(void) {
    int n, k, val;
    Node *node, *head = NULL, *cur = NULL;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &val);
        node = newNode(val);
        if (head == NULL) {
            head = cur = node;
            continue;
        }
        cur->next = node;
        cur = cur->next;
    }
    head = removeKthNode(head, k);
    cur = head;
    while (cur != NULL) {
        printf("%d", cur->val);
        cur = cur->next;
        if (cur != NULL)
            printf(" ");
    }
    printf("\n");
    freeList(head);
    return 0;
}

Node *newNode(int val) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

void freeList(Node *head) {
    Node *old;
    while (head != NULL) {
        old = head;
        head = head->next;
        free(old);
    }
}

Node *removeKthNode(Node *head, int k) {
    Node *cur = head, *pre = NULL, *old;
    for (int i = 1; i < k; i++) {
        pre = cur;
        cur = cur->next;
    }
    if (pre == NULL) {
        old = head;
        head = head->next;
    } else {
        old = pre->next;
        pre->next = pre->next->next;
    }
    free(old);
    return head;
}

发表于 2022-02-06 23:05:27 回复(0)
天运捷头像 天运捷
list_node * remove_kth_node(list_node * head, int K)
{
    //////在下面完成代码
    if(head==NULL)
    {
        return head;
    }
    if(K==1)
    {
        return  head->next;
    }
    list_node *p=head;
    while((--K)!=1) //找到要删除节点的上一个节点
    {
        p=p->next;
    }
    p->next=p->next->next;
    return head;
}
发表于 2021-06-24 10:52:46 回复(0)
Python
毓毓子最可爱头像 毓毓子最可爱 
n,m=map(int,input().split())
number_list=list(map(int,input().split()))
number_list.pop(m-1)
print(" ".join(map(str,number_list)))

发表于 2021-06-17 20:06:38 回复(0)
復活の検事头像 復活の検事 
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        Node node = new Node(scanner.nextInt());
        Node head = node;
        for(int i=1;i<n;i++) {
            Node next = new Node(scanner.nextInt());
            node.next = next;
            node = next;
        }
        StringBuilder sb = new StringBuilder();
        Node result = removeK(head, k);
        while(result != null) {
            sb.append(result.value).append(" ");
            result = result.next;
        }
        System.out.println(sb.toString().trim());
    }
    
    public static Node removeK(Node node, int k) {
        if(node == null || k<=0) {
            return node;
        }

        Node help = new Node(-1);
        help.next = node;
        Node fast = help;
        while(fast != null && k-- > 1) {
            fast = fast.next;
        }
        fast.next = fast.next.next;
        return help.next;
    }
}

class Node {
    public int value;
    public Node next;
    
    public Node(int data) {
        this.value = data;
    }
}
发表于 2021-04-21 18:49:41 回复(0)
p_string头像 p_string 
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] rawInput = br.readLine().trim().split(" ");
        
        int n = Integer.parseInt(rawInput[0]);
        int val = Integer.parseInt(rawInput[1]);
        if (val > n) {
            System.out.print("");
            br.close();
            return;
        }
        
        rawInput = br.readLine().trim().split(" ");
        // 构建链表节点
        Node head = buildLinkedList(rawInput);
        
        // 找到倒数第k个节点，并删除
        head = findAndDelKNode(head, val);
        // 打印输出链表节点的值
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb . append(head.value) . append(" ");
            head = head.next;
        }
        
        System.out.print(sb.toString().trim());
        
        br.close();
    }
    
    private static Node buildLinkedList(String[] elements) {
        Node head = null;
        if (0 == elements.length) {
            return head;
        }
        
        Node curNode = null;
        for (int i = 0; i < elements.length; i++) {
            Node node = new Node(Integer.parseInt(elements[i]));
            if (null == head) {
                head = node;
            } else {
                curNode.next = node;
            }
            curNode = node;
        }
        
        return head;
    }
    
    // 删除链路第K个节点的函数
    private static Node findAndDelKNode(Node head, int val) {
        if (null == head) {
            return head;
        }
        Node node = head;
        if (1 == val) {
            return head.next;
        }
        while (null != node.next && val > 2) {
            node = node.next;
            --val;
        }
        node.next = node.next.next;
        return head;
    }
}

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

发表于 2020-07-22 09:38:41 回复(0)
gapex头像 gapex 
Node *remove(Node *head, unsigned int k){
    //题设中假定k是合法值，所以这里就不处理异常情况了
    Node **pp = &head;
    while(--k){
        pp = &((*pp)->next);
    }
    shared_ptr<Node> target_ptr(*pp);
    *pp = target_ptr->next;
    return head;
}
发表于 2020-05-19 16:17:16 回复(0)
Java
菜就要努力头像 菜就要努力 
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        
        int n=in.nextInt();
        int m=in.nextInt();
        int temp=0;
        for(int i=0;i<n;i++){
            temp=in.nextInt();
            if(m==i+1){
                continue;
            }
            System.out.print(temp+" ");
        }
    }
}


发表于 2020-02-16 17:44:38 回复(0)
EVANnnn1996头像 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 removeKthNode(Node head, int kth) {
        if (head == null || kth < 1) {
            return head;
        }
        if (kth == 1) {
            return head.next;
        }
        Node cur = head;
        while (cur.next != null && kth > 2) {
            cur = cur.next;
            kth--;
        }
        if (kth == 2) {
            cur.next = cur.next.next;
        }
        return head;
    }

    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 main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] parameters = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(parameters[0]);
        int k = Integer.parseInt(parameters[1]);
        String[] numbers = bufferedReader.readLine().split(" ");
        Node head = listGenerator(n, numbers);
        head = removeKthNode(head, k);
        printList(head);
    }
}

不通过
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为90.00%
发表于 2019-12-22 16:29:06 回复(0)
Mr_Fourier头像 Mr_Fourier 
list_node * remove_kth_node(list_node * head, int K)
{
    //////在下面完成代码
    list_node * new_phead = new list_node();
	new_phead->next = head;
	list_node *p = new_phead;

	K--;
	while (K--) {
		p = p->next;
	}
	list_node *s = p->next;
	p->next = s->next;
	delete s;
	return new_phead->next;
}

发表于 2019-11-12 14:46:59 回复(0)
提交观点

问题信息

链表
上传者：小小
难度：
14条回答 5170浏览

热门推荐

通过挑战的用户

查看代码

相关试题

删除链表的中间节点

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号