在链表中删除倒数第K个节点_

pein531

先利用双指针找到倒数第k个节点，然后还是利用双指针将倒数第k个节点删除

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

class ListNode {
    public int val;
    public ListNode next;
    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().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        String[] strElem = br.readLine().split(" ");
        ListNode head = new ListNode(Integer.parseInt(strElem[0]));
        ListNode cur = head;
        for(int i = 1; i < n; i++){
            cur.next = new ListNode(Integer.parseInt(strElem[i]));
            cur = cur.next;
        }
        ListNode targetNode = tailKNode(head, k);
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        cur = head;
        while(cur != null) {
            if(cur == targetNode)
                prev.next = cur.next;
            prev = prev.next;
            cur = cur.next;
        }
        while(head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    
    public static ListNode tailKNode(ListNode head, int k) {
        ListNode first = head, second = head;
        for(int i = 1; i < k; i++)
            first = first.next;
        while(first.next != null){
            first = first.next;
            second = second.next;
        }
        return second;
    }
}

发表于 2021-05-31 11:10:10 回复(0)

C/C++

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_last_kth_node(list_node * head, int K){
    list_node *p = head;
    list_node *L = new list_node;
    L->next = head;
    for(int i=0;i<K-1;i++)
        p = p->next;
    if(p->next==NULL)
        return head->next;
    while(p->next->next){
        p = p->next;
        head = head->next;
    }
    head->next = head->next->next;
    return L->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_last_kth_node(head, K);
    print_list(rhead);
    return 0;
}

发表于 2020-03-15 02:56:57 回复(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 removeLastKthNode(Node head, int lastKth) {
        if (head == null || lastKth < 1) {
            return head;
        }
        Node slow = head;
        Node fast = head;
        while (fast.next != null && lastKth > 0) {
            fast = fast.next;
            lastKth--;
        }
        if (lastKth == 1) {
            head = head.next;
        } else if (lastKth == 0) {
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.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 = removeLastKthNode(head, k);
        printList(head);
    }
}

发表于 2019-12-22 15:36:44 回复(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 = node;
        Node slow = node;
        while(fast != null && k-- > 0) {
            fast = fast.next;
        }
        if(k > 0) {
            return help.next;
        }
        while(fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return help.next;
    }
}

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

发表于 2021-04-21 17:59:29 回复(0)

无心2019

# 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_last_kth_node(list_node * head, int K)
{
    //////在下面完成代码
    if(head==NULL)
        return NULL;
    list_node *phead=new list_node;
    phead->next=head;
    list_node* p1=head;
    list_node* p2=head;
    for(int i=0;i<K-1;i++)
        p1=p1->next;
    if(!p1)
        return NULL;
    if(!p1->next)
        return head->next;
    while(p1->next->next)
    {
        p1=p1->next;
        p2=p2->next;
    }
    p2->next=p2->next->next;
    return phead->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_last_kth_node(head, K);
    print_list(rhead);
    return 0;
}

发表于 2019-09-01 19:01:40 回复(0)

唉梅子

list_node * remove_last_kth_node(list_node * head, int K)
{
    //////在下面完成代码
    list_node * node = new list_node;
    node->next = head;
    //list_node * p = node;
    list_node * p1 = head;
    for(int i = 0;i < K-1;i++){
        p1 = p1->next;
    }
    if(p1->next == nullptr)
        return head->next;
    list_node * p2 = head;
    while(p1->next->next){
        p1 = p1->next;
        p2 = p2->next;
    }
    p2->next = p2->next->next;
    return node->next;
}

发表于 2019-08-02 19:22:54 回复(0)

C++

于涵。

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

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> v(n);

    for (int i = 0; i < n; ++i) {
        scanf("%d", &v[i]);
    }

    if (k > v.size() || v.empty()){
        for (int i = 0; i < n; ++i) {
            if (i != 0)
                printf(" ");
            printf("%d", v[i]);
        }
    } else{
        v.erase(v.begin() + (n - k));
        for (int i = 0; i < v.size(); ++i) {
            if (i != 0)
                printf(" ");
            printf("%d", v[i]);
        }
    }

    return 0;
}

发表于 2022-09-08 10:51:35 回复(0)

牛娃牛娃

list_node * remove_last_kth_node(list_node * head, int K)
{
    //////在下面完成代码
    list_node *dummynode=new list_node(0);
    dummynode->next =head;
    list_node *fast =dummynode;
    list_node *slow= dummynode;
    while(K&&fast!=nullptr){
        fast =fast->next;
        K--;
    }
    fast =fast->next;
    while(fast!=nullptr){
        slow =slow->next;
        fast =fast->next;
    }
    slow->next =slow->next->next;
    return dummynode->next;
}

发表于 2022-05-23 20:29:32 回复(0)

C++

木子蓝色

使用快慢指针，快指针先走K步，然后再让快慢指针同时前进，当快指针走到结尾时，慢指针的下一步就是要删除的节点

list_node * remove_last_kth_node(list_node * head, int K)
{
    list_node* fast = head;
    list_node* slow = head;
        //快指针先走K步
    while(K--){
        fast = fast->next;
    }
        //快指针为空，说明是要删除头结点，直接返回
    if(fast == nullptr) return head;
        // 让快慢指针同时前进
    while(fast->next != nullptr){
        fast = fast->next;
        slow = slow->next;
    }
        //慢指针的下一步就是要删除的节点
    list_node* tmp = slow->next;
    slow->next = slow->next->next;
    delete tmp;
    return head;
}

发表于 2022-04-08 10:44:58 回复(0)

C

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 *removeLastK(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 = removeLastK(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 *removeLastK(Node *head, int k) {
    Node *fast = head;
    Node *slow = head;
    Node *pre = NULL, *old;
    for (int i = 0; i < k; i++) {
        fast = fast->next;
    }
    while (fast != NULL) {
        pre = slow;
        slow = slow->next;
        fast = fast->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 22:49:01 回复(0)

Python

毓毓子最可爱

n,m=map(int,input().split())
a=list(map(int,input().split()))
#python中负号代表倒数
a.pop(-1*m)
print(" ".join(map(str,a)))

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

思考致富

/*
 * @Description: 在链表中删除倒数第K个结点
 * @Author: 
 * @Date: 2020-11-08 20:07:10
 * @LastEditTime: 2020-11-08 20:33:09
 * @LastEditors: Please set LastEditors
 */
#include <iostream>
using namespace std;

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

int K, n, val;

list_node *input_list(void) //读入链表
{

    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_last_kth_node(list_node *head, int K)
{
    //在下面完成代码
    int k = n - K;//倒数第k个结点
    list_node *pre = NULL;//前一个结点
    list_node *curr = head;//当前结点
    for(int i = 0;i < k;i++){
        pre = curr;
        curr = curr->next;
    }
    if (pre == NULL)
    {
        head = curr->next;
        delete curr;//删除结点
        curr = NULL;//避免称为野指针
    }else{
        pre->next = curr->next;
        delete curr;
        curr = NULL;
    }
    return head;
}

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_last_kth_node(head, K);
    print_list(rhead);
    return 0;
}

发表于 2020-11-08 20:34:38 回复(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));
        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 = findAndDelLastKNode(head, n, 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;
    }
    
    private static Node findAndDelLastKNode(Node head, int n, int val) {
        if (null == head) {
            return head;
        }
        
        // 倒数第n个节点特殊处理
        if (val == n) {
            Node node = head;
            head = head.next;
            node = null; // 避免对象的游离
            return head;
        }
        
        //由于是单链表，要查到倒数第 k + 1节点，以方便后序节点赋值处理
        int i = 0;
        Node curNode = head;
        // 先查找正数第k + 1个节点
        while (i < val + 1) {
            curNode = curNode.next;
            i++;
        }
        
        Node lastNode = head;
        while (curNode != null) {
            curNode = curNode.next;
            lastNode = lastNode.next;
        }
        
        Node lastKNode = lastNode.next;
        lastNode.next = lastKNode.next;
        lastKNode = null;
        
        return head;
    }
}

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

发表于 2020-07-18 23:38:11 回复(0)

C/C++

别搁那忽悠人了

list_node * remove_last_kth_node(list_node * head, int K)
{
    //////在下面完成代码
    list_node* quick = head;
    list_node* slow = head;

    for (int i = 0;i < K;i++){
        quick = quick->next;
    }

    while (quick->next != NULL){
        quick = quick->next;

slow = slow->next;

}

slow->next = slow->next->next;
return head;

}

发表于 2020-03-26 16:21:07 回复(0)

offer来了哦哦哦

import java.util.*;
import java.io.*;
public class Main
{ //这样为什么还慢，运行时间：3821ms占用内存：160640k


    public static void main(String [] araa){
          Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            int n = sc.nextInt();

            int m = sc.nextInt();
            int i = 0;
            while(i<n){
               int v  = sc.nextInt();
               //等同正的数第n-m+1个，因位置从0开始，删除的位置就是n-m
               if(i != n-m)
                   System.out.print(v+" ");
                i++;
            }
             System.out.println();
        }
    }
}

编辑于 2019-10-06 23:09:53 回复(0)

尘总的小迷弟

个人觉得这种题目如果是机试场景下可以直接用数组来做解答。

本题目的难点在于需要删除的是第一个节点，这时候需要添加一个头指针。来帮助完成这项工作

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null||n==0){
            return head;
        }
        if(head.next==null&&n==1){
            return null;
        }
        ListNode pre=new ListNode(-1);
        pre.next=head;
        ListNode fast=pre;
        ListNode slow=pre;
        while(n-->0){
            fast=fast.next;
        }
        while(fast!=null&&fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return pre.next;
    }
}

发表于 2019-08-18 11:06:53 回复(0)

在链表中删除倒数第K个节点

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题