题目描述:
输入一个链表,输出该链表中倒数第k个结点。
(hint: 请务必使用链表。)
输入:
输入可能包含多个测试样例,输入以EOF结束。
对于每个测试案例,输入的第一行为两个整数n和k(0<=n<=1000, 0<=k<=1000):n代表将要输入的链表元素的个数,k代表要查询倒数第几个的元素。
输入的第二行包括n个数t(1<=t<=1000000):代表链表中的元素。
输出:
对应每个测试案例,
若有结果,输出相应的查找结果。否则,输出NULL。
样例输入:
5 2
1 2 3 4 5
1 0
5
样例输出:
4
NULL
【解析】
【代码】
/*********************************
* 日期:2013-11-20
* 作者:SJF0115
* 题号: 题目1517:链表中倒数第k个结点
* 来源:http://ac.jobdu.com/problem.php?pid=1517
* 结果:AC
* 来源:剑指Offer
* 总结:
**********************************/
#include<iostream>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
using namespace std;
typedef struct ListNode{
int value;
struct ListNode *next;
}ListNode;
int FindKthToTail(ListNode*head,int k){
//容错处理
if(head == NULL || k <= 0){
return NULL;
}
else{
ListNode *p,*pre;
//带头节点的链表
pre = p = head->next;
//第一个指针向前走k-1步,第二个指针保持不变
for(int i = 0;i < k-1;i++){
p = p->next;
}
//两个指针同时向前遍历
while(p->next != NULL){
pre = pre->next;
p = p->next;
}
return pre->value;
}
}
int main()
{
int i,n,k;
while(scanf("%d %d",&n,&k) != EOF){
ListNode *head,*p,*pre;
head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
pre = head;
for(i = 0;i < n;i++){
p = (ListNode*)malloc(sizeof(ListNode));
scanf("%d",&p->value);
p->next = NULL;
pre->next = p;
pre = p;
}
//全部输出
if(n < k){
printf("NULL\n");
}
else{
//倒数K个
int num = FindKthToTail(head,k);
if(num == NULL){
printf("NULL\n");
}
else{
printf("%d\n",num);
}
}
}
return 0;
}
分享到:
相关推荐
剑指Offer(Python多种思路实现):链表中倒数第k个节点 面试22题: 题目:链表中倒数第k个节点 题:输入一个链表,输出该链表中倒数第k个结点。 解题思路一:为了实现只遍历链表一次就能找到倒数第k个节点,我们可以...
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
【Python学习-链表】【剑指offer】之链表中倒数第k个结点、反转链表、合并排序链表题目分析代码反转链表分析代码合并排序链表分析代码 题目 输入一个链表,输出该链表中倒数第k个结点。 分析 方法一:先计数,在查询...
然后先让第一个指针first走k-1步,然后两个指针再一起走,当第二个指针second走到末尾(second.next = null)时,第一个指针first就
题目地址:链表中倒数第k个结点 题目描述 输入一个链表,输出该链表中倒数第k个结点。 节点结构如下: public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } ...
链表中倒数第k个结点(python) 题目 输入一个链表,输出该链表中倒数第k个结点。 思路 用两个指针,指针p、q最开始都指向 head,p 先向右移动 k 位,然后 p 和 q 再一起同步向右移动,当 p 到达边界时(p指向空),...
面试题15 链表中倒数第k个结点 面试题16 反转链表 面试题17 合并两个排序的链表 面试题18 树的子结构 第4章 解决面试题思路 4.2 画图让抽象问题形象化 面试题19 二叉树的镜像 面试题20 顺时针打印矩阵 4.3 举例让...
使用「快慢指针/双指针」可以很容易处理:「找出链表中环的入口结点」、「删除倒数第 K 个结点」等问题。 而树的「前序遍历」、「中序遍历」、「后序遍历」都有不同的特点,前序遍历和中序遍历的结合可以帮我们解决...
链表中倒数第k个结点 代码的鲁棒性 15 反转链表 代码的鲁棒性 LeetCode 206 16 合并两个排序的链表 代码的鲁棒性 17 树的子结构 代码的鲁棒性 18 二叉树的镜像 面试思路 19 顺时针打印矩阵 画图让抽象形象化 ...
Interviews(剑指offer Java代码)二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的最小数字斐波那契数列跳台阶变态跳台阶矩形覆盖二进制中1的个数数值的整数次方调整数组顺序使奇数...
15链表中倒数第k个结点 16反转链表 17合并两个排序的链表 18树的子结构 19二叉树的镜像 20顺时针打印矩阵 21包含min函数的栈 22栈的压入弹出序列 23从上往下打印二叉树 24二叉搜索树的后序遍历序列 25二叉树中和为某...
快慢指针,比如,返回一个链表的中间节点,倒数第k个节点,有环结点,向右旋转的链表这些题目。 通常要分别选取列表长度为奇数、偶数的测试用例,以验证算法在一般情况下正确性。 使用链表 Queue queue=new ...
leetcode和剑指 Algorithm ...14.单链表:链表中倒数第k个结点 15.单链表:反转链表 16.单链表:合并两个排序的链表 17.二叉树:树的子结构 18.二叉树:二叉树的镜像 19.顺时针打印矩阵 20.栈:包含min函数的栈
判断青蛙过河leetcode ads_java Algorithms and Data Structures 参考资料 《数据结构与算法经典问题解析-Java语言描述 第二版》 《数据结构与算法分析-Java语言描述 第二版》 ...链表中倒数第k个结点 反转
14.链表中倒数第k个结点 题目: 答案: 16.合并两个排序的链表 题目: 答案: 18.二叉树的镜像 题目: 答案: 36.两个链表的第一个公共结点 题目: 答案: 38.二叉树的深度 题目: 答案: 39.平衡二叉树 题目: 答案...
leetcode 苹果 OnlineJudge Code for ...链表中倒数第k个结点 中 代码的鲁棒性 反转链表 中 代码的鲁棒性 合并两个排序的链表 难 代码的完整性 数值的整数次方 中 举例让抽象具体化 栈的压入、弹出序
5、删除链表倒数第 n 个结点 6、求单向链表的中间结点 二、栈 1、Java实现顺序栈、链式栈 三、队列 1、顺序队列、链式队列 2、循环队列 四、排序算法 1、冒泡排序 2、插入排序 3、选择排序 4、归并排序 5、快速排序 ...