本文主要是介绍AcWing 33：链表中倒数第k个节点 ← 尾插法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目来源】
https://www.acwing.com/problem/content/32/
【题目描述】
输入一个链表，输出该链表中倒数第 k 个结点。
注意：
● k >= 1;
● 如果 k 大于链表长度，则返回 NULL；
【数据范围】
链表长度 [0,30]。
【输入样例】
输入：链表：1->2->3->4->5 ，k=2
【输出样例】
输出：4
【算法分析】
● 假设链表有 n 个结点，那么只要从头结点开始往后走 n-k 步就可以到达倒数第 k 个结点（从 1 开始计数）。
● 头插法及尾插法
头插法创建单链表：https://blog.csdn.net/hnjzsyjyj/article/details/120285274
尾插法创建单链表：https://blog.csdn.net/hnjzsyjyj/article/details/120285300
本题算法，选用尾插法建立单链表。
● 适应本例类风格的代码如下所示：
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {public:ListNode* findKthToTail(ListNode* head, int k) {int cnt=0;ListNode* p=head;while(p) {cnt++;p=p->next;}if(cnt<k) return NULL; //nullptrp=head;for(int i=0; i<cnt-k; i++) p=p->next;return p;}
};
【利用尾插法构建单链表后求解的完整代码】
#include <bits/stdc++.h>
using namespace std;struct LNode {int data;LNode *next;
};
typedef struct LNode *LinkList;void Tail_Insert(LinkList &L) {L=new LNode;L->next=NULL;LinkList r=L;printf("Input value:");int x;while(scanf("%d",&x)!=EOF) {LinkList p;p=new LNode;p->data=x;p->next=NULL;r->next=p;r=p;}
}void findKthToTail(LinkList &L,int k) {LinkList tail=L, head=L;if(k<=0) {printf("Input error!\n");return;}for(int i=1; i<=k; i++) {tail=tail->next;if(tail==NULL) {printf("No such node!\n");return;}}while(tail!=NULL && head!=NULL) {tail=tail->next;head=head->next;}printf("%d\n",head->data);
}int main() {int k;LinkList L=new LNode;L->next=NULL;Tail_Insert(L);printf("Input k:");while(scanf("%d",&k)!=EOF) {findKthToTail(L,k);printf("Input k:");}return 0;
}/*
Input value:9 6 2 8 5
^Z
Input k:3
2
Input k:2
8
Input k:5
9
Input k:1
5
Input k:12
No such node!
Input k:-12
Input error!
Input k:
*/
【参考文献】
https://blog.csdn.net/zwb8848happy/article/details/7330586
https://www.acwing.com/video/2698/
这篇关于AcWing 33：链表中倒数第k个节点 ← 尾插法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
