本文共 1808 字,大约阅读时间需要 6 分钟。
地址:http://ac.jobdu.com/problem.php?pid=1517
题目1517:链表中倒数第k个结点
输入一个链表,输出该链表中倒数第k个结点。
(hint: 请务必使用链表。)
输入可能包含多个测试样例,输入以EOF结束。
对于每个测试案例,输入的第一行为两个整数n和k(0<=n<=1000, 0<=k<=1000):n代表将要输入的链表元素的个数,k代表要查询倒数第几个的元素。 输入的第二行包括n个数t(1<=t<=1000000):代表链表中的元素。
对应每个测试案例,
若有结果,输出相应的查找结果。否则,输出NULL。
5 21 2 3 4 51 05
4NULL
使用两个指针,两个指针间相差k个节点,当其中一个指针指向最后一个节点时,另一个节点指向链表倒数第k个节点。
注意检查特殊情况:
1、链表为空
2、k为0
3、k大于链表的长度
#include #include struct listNode { int data; listNode *next;};listNode* findK(listNode* head, int k) { if(head->next == NULL || k == 0) return NULL; listNode *p = head; listNode *q = head->next; bool flag = false; for(int i = 1; i <= k; i ++) { if(p->next == NULL && i <= k) { flag = true; break; } else p = p->next; } if(flag) return NULL; else { while(p->next != NULL){//不可以写成!p->next p = p->next; q = q->next; } return q; }}int main() { int n; int k; while(scanf("%d %d", &n, &k) != EOF) { listNode *head = (listNode *)malloc(sizeof(listNode)); head ->data = 0; head ->next = NULL; listNode *p = head; listNode *q = head; for(int i = 0; i < n; i ++) { p = (listNode *)malloc(sizeof(listNode)); scanf("%d", &p->data); p->next = NULL; q->next = p; q = q->next; } p = findK(head, k); if(p != NULL) printf("%d\n", p->data); else printf("NULL\n"); } return 0;}/************************************************************** Problem: 1517 Language: C++ Result: Accepted Time:100 ms Memory:2604 kb****************************************************************/
转载地址:http://zesob.baihongyu.com/