首页 > 代码库 > 链表中倒数第k个结点
链表中倒数第k个结点
问题
从1开始计数，计算倒数第k个结点的指针。例如：
思路
整着数到第k，然后前后一块往后走，前边的走到头，后边的极为倒数第k个结点，图示
注意
- 传入空指针
- k大于结点的个数
代码
ListNode* LastNNode(ListNode *root, int n){ if (root == NULL || n <=0) return NULL; ListNode *cur = root; ListNode *pre = root; int cnt = 0; while (pre != NULL) { cnt++; if (cnt == n) break; pre = pre->next; } if (cnt < n) { return NULL; } else { cur = root; while (pre->next != NULL) { pre = pre->next; cur = cur->next; } return cur; }}
执行
#include <iostream>using namespace std;struct ListNode{ int val; ListNode *next; ListNode(int v) : val(v), next(NULL) {}};ListNode* LastNNode(ListNode *root, int n){ if (root == NULL || n <=0) return NULL; ListNode *cur = root; ListNode *pre = root; int cnt = 0; while (pre != NULL) { cnt++; if (cnt == n) break; pre = pre->next; } if (cnt < n) { return NULL; } else { cur = root; while (pre->next != NULL) { pre = pre->next; cur = cur->next; } return cur; }}ListNode* createList(){ ListNode *root = new ListNode(0); ListNode *p1 = new ListNode(1); ListNode *p2 = new ListNode(2); ListNode *p3 = new ListNode(3); root->next = p1; p1->next = p2; p2->next = p3; return root;}void deleteList(ListNode *root){ ListNode *p = root; while(root != NULL) { p = root->next; delete(root); root = p; }}void tranverse(ListNode* root){ while(root != NULL) { cout << root->val << " "; root = root->next; } cout << endl;}int main(){ ListNode *root = createList(); root = NULL; ListNode *p = LastNNode(root, 1); cout << p << endl; if (p != NULL) cout << p->val << endl; deleteList(root);}
推荐
算法与数据结构索引
链表中倒数第k个结点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。