输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
}; 正常返回倒数第k个结点指针，异常返回空指针.
要求：
(1)正序构建链表;
(2)构建后要忘记链表长度。
数据范围：链表长度满足 
， 
，链表中数据满足 
本题有多组样例输入。
[编程题]输出单向链表中倒数第k个结点
#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)
#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)
#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)
#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)
#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;
}
#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)
#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)
#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)
#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;
}
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)
#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)
倒数第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
回复(2)
#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;
}
#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)
#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)
问题信息
难度：
16条回答
1974收藏
43230浏览
通过挑战的用户
查看代码-
2022-12-17 11:53:31 -
2022-10-27 18:28:26 -
2022-10-10 21:39:13
-
2022-10-10 11:22:33
-
2022-09-22 20:38:57
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
