首页 > 试题广场 >

输出单向链表中倒数第k个结点

[编程题]输出单向链表中倒数第k个结点
  • 热度指数：235705 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。

链表结点定义如下： 
struct ListNode
{
    int val;
    ListNode* m_pNext;
};
正常返回倒数第k个结点指针。

输入描述:
每一个测试用例会有多组。每一组的测试用例格式如下：
第一行输入链表结点个数， 
第二行输入长度为的数组，表示链表的每一项， 
第三行输入的值， 


输出描述:
每一组，输出倒数第k个结点的值
示例1

输入

3
1 2 3
1
8
1 2 3 4 5 6 7 8
4

输出

3
5
算法知识视频讲解
查看答案及解析
添加回答
C
人生有三乐头像 人生有三乐 
#include <stdio.h>
//直接用数组写，考试时可没那么多时间给你好吧，快速解决留更多的时间给中等题
int main() {
    int n;
    int a[1000];
    while (scanf("%d", &n) != EOF) { 
        for (int i=0; i<n; i++) {
            scanf("%d",&a[i]);
        }
        int k;
        scanf("%d",&k);
        printf("%d\n",a[n-k]);
    }
    
}

发表于 2025-10-11 10:48:29 回复(0)
C
在泡澡的卡尔很放浪头像 在泡澡的卡尔很放浪
#include <stdio.h>
#include<stdlib.h>
typedef struct ListNode
{
    int val;
    struct ListNode* m_pNext;
}ListNode;

ListNode* Creaknode(ListNode** pphead, int x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->m_pNext = NULL;
    newnode->val = x;
    if (*pphead == NULL)
        *pphead = newnode;
    else
    {
        ListNode* cur = *pphead;
        while (cur->m_pNext)
        {
            cur = cur->m_pNext;
        }
        cur->m_pNext = newnode;
    }
    return *pphead;
}

int main() {
    int n = 0;
    int arr[1000];
    int k = 0;
    ListNode* head = NULL;
    while(~scanf("%d", &n)){
    for (int i = 0;i < n;i++)
    {
        scanf("%d", &arr[i]);
        head = Creaknode(&head, arr[i]);
    }
    scanf("%d", &k);
    ListNode* frist = head;
    ListNode* slow = head;
   
        while (k--)
            frist = frist->m_pNext;
    while (frist && frist->m_pNext)
    {
            frist = frist->m_pNext;
        slow = slow->m_pNext;
    }
    if(head->m_pNext==NULL)
    printf("%d\n",slow->val);
    else
        printf("%d\n", slow->m_pNext->val);
    }
    return 0;
}
发表于 2025-02-03 15:13:50 回复(0)
C
墨夜风名头像 墨夜风名 
#include <stdio.h>
#include <stdlib.h>

struct ListNode
{
    int m_nKey;
    struct ListNode *m_pNext;
};

void insertNode(struct ListNode *head, int value)
{
    struct ListNode *next = head->m_pNext;
    struct ListNode *prev = head;
    for(; next != 0; next = next->m_pNext){
        prev = next;
    }

    struct ListNode *temp = malloc(sizeof(struct ListNode));
    temp->m_nKey = value;
    temp->m_pNext = prev->m_pNext;
    prev->m_pNext = temp;
    return ;
}

int main() {
    int num;
    struct ListNode *head;

    head = malloc(sizeof(struct ListNode));
    head->m_nKey = -1;
    head->m_pNext = 0;

    while(scanf("%d", &num) != EOF){
        int value;

        for(int i=0;i<num;i++){
            scanf("%d", &value);
            insertNode(head, value);
        }

        int index = 0;
        scanf("%d", &index);
        //1 2 3 4 5 6 7 8
        struct ListNode *front = head->m_pNext;
        struct ListNode *back = head->m_pNext;

        while(index--){
            front = front->m_pNext;
        }

        while (front) {
            front = front->m_pNext;
            back = back->m_pNext;
        }
        printf("%d\n", back->m_nKey);
    }
    return 0;
}

编辑于 2024-02-26 17:28:11 回复(0)
C
宇g头像 宇g 
#include <stdio.h>
#include <stdlib.h>

typedef struct linklist{
    int value;
    struct linklist *next;
}link;

int main()
{
    int num, k, i;
    int in[1000];

    while(scanf("%d",&num) != EOF)
    {
    for(i=0;i<num;i++)
    {
        scanf("%d",&in[i]);
    }
    scanf("%d",&k);
    link *head, *normal;
    head=(link*)malloc(sizeof(link));
    head->value=in[0];
    link *p=head;
    for(i=1;i<num;i++)           //创建链表
    {
        normal=(link*)malloc(sizeof(link));
        normal->value=in[i];
        p->next=normal;
        normal->next=NULL;
        p=p->next;
    }
    link *fast=head;             //快指针先走到第k个结点
    i=1;
    while(i<k)
    {
        fast=fast->next;
        i++;
    }
    link *slow=head;             //慢指针和快指针一起走，快指针走到最后一个结点跳出循环
    while(fast->next != NULL)
    {
        fast=fast->next;
        slow=slow->next;
    }
    printf("%d\n",slow->value);
    }

    return 0;
}

发表于 2023-12-04 18:36:05 回复(0)
C
猪猪侠的飞天梦头像 猪猪侠的飞天梦 
#include <stdio.h>
int main() {
    int n = 0, a[1000] = {0}, k = 0;
    while (scanf("%d", &n)!= EOF) {
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        scanf("%d", &k);
        printf("%d\n", a[n - k]);
    }
    return 0;
}

发表于 2023-12-02 22:59:56 回复(4)
C
planetlight头像 planetlight
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *next;
}list,*listpoint;

listpoint list_createhead(int x){
    listpoint lhead=(listpoint)malloc(sizeof(list));
    lhead->data=x;
    lhead->next=NULL;
    return lhead;
}

void list_create(listpoint lhead, int x){
    listpoint tail=lhead;
    while(tail->next){
        tail=tail->next;
    }
    listpoint newcode=(listpoint)malloc(sizeof(list));
    newcode->data=x;
    newcode->next=NULL;
    tail->next=newcode;
}  

void list_numfind(listpoint lhead,int num,int pos){
    listpoint H=lhead;
    int i=0;
    int j=num-pos;
    while(H){
        if(i==j){
            printf("%d\n",H->data);
            return ;
        }
        else {
            H=H->next;
            i++;
        }
    }
}

int main() {
    int num=0;
    while(scanf("%d",&num) !=EOF){
        int headnum=0;
        scanf("%d",&headnum);
        listpoint lhead=list_createhead(headnum);
        int i=1;
        while(i<num){
            int x=0;
            scanf("%d",&x);
            list_create(lhead,x);
            i++;
        }

        int findnum=0;
        scanf("%d",&findnum);
        list_numfind(lhead,num,findnum);
    }
   
    return 0;
}
发表于 2023-05-22 21:46:46 回复(0)
C
初牛小客头像 初牛小客 
#include <stdio.h>

typedef struct LinkList{
    int data;
    struct LinkList *next;
} *LinkList, LNode;

int main() {
    int n;

    while(scanf("%d", &n) != EOF)
    {
        LinkList L = (LinkList)malloc(sizeof(LinkList));    //初始化头结点
        L->next = NULL;

        for(int i=0; i<n; i++){
            LNode* node = (LNode*)malloc(sizeof(LNode));
            scanf("%d", &node->data);
            node->next = NULL;

            LNode* p = L;
            while(p->next)
            {
                p = p->next;    //找到最后一个结点
            }
            p->next = node;     //尾插法
        }

        int k;
        scanf("%d", &k);
        LNode* fast = L;
        LNode* low = L;
        int step = 0;
        while(step < k)    //快指针先走k步
        {
            fast = fast->next;
            step++;
        }
        
        while(fast)       //快、慢指针一起走，直到快指针为空，此时慢指针就是倒数第k个结点
        {
            low = low->next;
            fast = fast->next;
        }
        printf("%d\n", low->data);
    }
    return 0;
}

发表于 2023-03-02 19:59:29 回复(0)
C
好久不见，最近好吗头像 好久不见，最近好吗
#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode
{
    int m_nKey;
    struct ListNode *m_pNext; 
}List,*pList;

pList Creat_List(int node_n)
{
    int data;
    pList L_head = NULL,tmp = NULL,tail = NULL;
    while(node_n--)
    {
        tmp = (pList)malloc(sizeof(struct ListNode)); 
        if(!tmp)
        {
            return NULL;
        }
        scanf("%d",&data);
        tmp->m_nKey = data;
        tmp->m_pNext = NULL;
        if(L_head == NULL )
        {
            L_head = tmp;
        }
        else
        {
            if(L_head->m_pNext == NULL)
            {
                L_head->m_pNext = tmp;
            }
            else
            {
                tail->m_pNext = tmp;
            }
        }
        tail = tmp;
    }
    return L_head;
}

int get_node_keyval(pList list,int r_k)
{
    int len = 0,pos = 0,i = 0;
    pList p =  list;
    while(p->m_pNext != NULL)
    {
        len++;
        p = p->m_pNext;
    }
    pos = len - r_k + 1; 
    p = list;
    for(i = 0;i < pos; i++)
    {
        p = p->m_pNext;
    }
    return p->m_nKey;
}
int main(void)
{
    int node_num = 0;
    int tail_k;
    int i = 0;
    int val = 0;

    while(scanf("%d",&node_num) != EOF)
    {
        if(node_num < 1) break;
        pList list_h = Creat_List(node_num);
        if(!list_h)
        {
            return -1;
        }
        scanf("%d",&tail_k);
        val = get_node_keyval(list_h,tail_k);
        printf("%d\n",val);
    }
    return 0;   
}
发表于 2022-06-17 11:50:25 回复(0)
C
凉风有兴头像 凉风有兴 
#include <stdio.h>

struct ListNode
{
    int m_nKey;
     struct ListNode* m_pNext;
};

int main(){
    struct ListNode *head = NULL, *tmp, *p;
    int num;
    int m_nKey;
    int i = 0;
    int k;
    while(scanf("%d", &num) != EOF){
        for(i = 0; i  < num; i++){
            p = (struct ListNode *)malloc(sizeof(struct ListNode));
            scanf("%d", &m_nKey);
            p->m_nKey = m_nKey;
            p->m_pNext = NULL;
            if(head == NULL)
                head = p;
            else
                tmp->m_pNext = p;
            tmp = p;
        }
        tmp = head;
        scanf("%d", &k);
        for(i = 0; i < num-k;i++){
            tmp = tmp->m_pNext;
        }
        printf("%d", tmp->m_nKey);
        while(head != NULL){
            tmp = head;
            head = tmp->m_pNext;
            free(tmp);
        }
        printf("\n");
    }
    return 0;
}

发表于 2022-05-15 19:18:08 回复(0)
C
胡涂涂~头像 胡涂涂~ 
#include<stdio.h>

struct ListNode
{
    int m_nKey;
    struct ListNode* m_pNext;
};

struct ListNode*  listinit(int headval){
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode)) ;
    head->m_nKey = headval ;
    head->m_pNext = NULL ;
    return head ;
}

void listadd(int val,struct  ListNode*head){
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode)) ;
    node->m_nKey = val ;
    node->m_pNext = NULL ;
    head->m_pNext = node ;
    return ;
}

int main(){
    int n ;
    int val ;
    while(scanf("%d", &n) != EOF){
    scanf("%d",&val) ;

    struct ListNode* head = listinit(val) ;
    struct ListNode* k = head ;
    for(int i = 0;i<n-1 ; i++){
        scanf("%d",&val) ;
        listadd(val, k) ;
        k = k->m_pNext ;
    }
    int kk ;
    scanf("%d",&kk) ;
    struct ListNode* quetnode = head ;
    struct ListNode* slownode = head ;
    for(int i = 0;i<kk-1 ; i++){
        if(!quetnode) return 0 ;
        quetnode = quetnode->m_pNext ;
    }
    while(quetnode->m_pNext){
        quetnode = quetnode->m_pNext ;
        slownode = slownode->m_pNext ;
    }
    printf("%d\n",slownode->m_nKey) ;
}
    return 0 ;
}

发表于 2022-05-10 14:11:21 回复(0)
C
白丹丹头像 白丹丹
#include <stdio.h>

typedef struct {
    int value;
    struct ListNode *next;    
}ListNode;

int main()
{
    ListNode *temp = NULL;
    ListNode *ptr = NULL;
    ListNode *p = NULL;
    int i, n, k, value;
    
    while (scanf("%d", &n) != EOF) {       
        value = 0;
        k = 0;
        
        ListNode *head = malloc(sizeof(ListNode));       
        // ptr赋初值，指向头结点
        ptr = head;
        // 创建单向链表
        for (i = 0; i < n; i++) {
            scanf("%d", &value);
            temp = malloc(sizeof(ListNode));
            // 初始化每次申请的新结点
            temp->value = value;
            temp->next = NULL;
            // 把申请到的新结点挂到前面结点的后面
            ptr->next = temp;
            // ptr指针后移，指向当前新挂上去的结点
            ptr = ptr->next;
        }
        scanf("%d", &k);        
        // 查询链表某个结点
        i = 0;
        ptr = head->next;
        while (ptr != NULL) {
            i++;
            if (i == n - k + 1) {
                printf("%d\n", ptr->value);
            }
            ptr = ptr->next;
        }
        
        ptr = head->next;
        while (ptr != NULL) {
            // 先保存当前指针，并移动当前指针
            p = ptr;
            ptr = ptr->next;
            // 然后再释放内存
            free(p);
        }
    }
    
    return 0;
}
发表于 2022-05-04 12:54:02 回复(0)
C
阿金要努力头像 阿金要努力 
#include<stdio.h>
//定义一个单链表
typedef struct Listnode
{
    int data;
    struct Listnode* next;
}Listnode;
int returnback(Listnode*head,int n,int k)
{
    Listnode* tail=head;
    if(k>n||k==0)
        return NULL;
    for(int i=0;i<k-1;i++)
    {
        tail=tail->next;
    }
    return tail->data;
}
int main()
{
    int n=0,k=0;
    while(scanf("%d",&n)!=EOF)
    {
        Listnode* head=NULL;
        for(int i=0;i<n;i++)
        {
            Listnode* newnode=(Listnode*)malloc(sizeof(Listnode));
            scanf("%d",&newnode->data);
            newnode->next=head;
            head=newnode;
        }
        scanf("%d",&k);
        printf("%d\n",returnback(head, n, k));
    }
    return 0;
}

发表于 2022-04-13 16:46:53 回复(0)
C
虚戈戈头像 虚戈戈
倒数第k个就是正数第N-k+1个（数组下标N-k），用链表的话是正着数到第N-k+1个节点
不明白这题和链表有啥关系呢？靠scanf和printf输入与检测的，具体数据结构咋实现的都无所谓吧，用数组也能简单实现呀 
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int N;
    int k;
    int i;
    int arr[1001] ={0};
    while(EOF!=scanf("%d",&N))
    {
        for(i=0;i<N;i++)
        {
            scanf("%d",&arr[i]);
        }
        scanf("%d",&k);
        
        printf("%d\n",(k<=0||k>N)?0:arr[N-k]);
    }
    return 0;
}



发表于 2022-01-08 20:10:00 回复(3)
C
牛客354105004号头像 牛客354105004号
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
    int m_nKey;
    struct ListNode* m_pNext;
}ListNode;

int main() {
    int len;
    while(scanf("%d", &len) != EOF) {
        ListNode *head = (ListNode*)malloc(sizeof(ListNode));
        scanf("%d", &(head->m_nKey));
        head->m_pNext = NULL;
        ListNode *p;
        ListNode *q = head;
        for (int i = 0; i < len - 1; i++) {
            ListNode *p = (ListNode*)malloc(sizeof(ListNode));
            scanf("%d", &(p->m_nKey));
            p->m_pNext = q->m_pNext;
            q->m_pNext = p;
            q = p;
        }
        int k;
        scanf("%d", &k);
        p = head;
        if (k > 0) {
            while (len - k) {
                p = p->m_pNext;
                k++;
            }
            printf("%d\n", p->m_nKey);
        } else {
            printf("0\n");
        }
    }
    return 0;
}
发表于 2021-10-10 20:52:06 回复(0)
C
校长_头像 校长_ 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ListNode
{
    int Key;
    struct ListNode *next;
}ListNode, *List;

int main()
{
    int len = 0;
    int pos = 0;
    List L1 = NULL;
    ListNode *p = NULL;
    while(scanf("%d", &len) != EOF)
    {
        L1 = (ListNode*)malloc(sizeof(ListNode));
        L1->next = NULL;
        for(int i=0; i < len; i++)
        {
            p = (ListNode*)malloc(sizeof(ListNode));
            scanf("%d", &(p->Key));
            p->next = L1->next;
            L1->next = p;
        }
        scanf("%d", &pos);
        p = L1;
        for(int i=1; i<= pos; i++)
        {
            p = p->next;
        }
        printf("%d\n", p->Key);
        /*释放内存--删除操作*/
        for(int i=0; i<len; i++)
        {
            p = L1->next;
            L1->next = p->next;
            free(p);
        }
        free(L1);
    }
    
}

发表于 2021-07-23 22:15:18 回复(0)
提交观点

问题信息

链表 双指针
难度：
18条回答 48535浏览

热门推荐

通过挑战的用户

查看代码

相关试题

输出单向链表中倒数第k个结点

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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