22. 链表中倒数第k个节点

2020-06-20

1.题目描述

难度简单46收藏分享切换为英文关注反馈输入一个链表，输出该链表中倒数第k个节点。为了符合大多数 人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点 开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

2.题解

1.首先统计链表的长度cnt，然后得到正数第cnt-k+1个即可 2.双指针法

3.代码

class Solution { public:ListNode* getKthFromEnd(ListNode* head, int k) {int cnt=0;ListNode* p=head;while (p){p=p->next;cnt++;}if (k>cnt) return NULL;int i=1;p=head;while (p){if (i==cnt-k+1) break;i++;p=p->next;}return p;} }; class Solution { public:ListNode* getKthFromEnd(ListNode* head, int k) {if (!head) return NULL;ListNode *p=head;int cnt=1;while (p&&cnt<k){p=p->next;cnt++;}if (!p) return NULL;ListNode *q=head;while (p->next){p=p->next;q=q->next;}return q;} };

总结

以上是生活随笔为你收集整理的22. 链表中倒数第k个节点的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。