LeetCode刷题（164）～链表中倒数第k个节点【递归｜ 双指针】

题目描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

  

 

  
1
  
2
  
3
 

解答 By 海轰

提交代码（两次遍历）

ListNode* getKthFromEnd(ListNode* head, int k) { int count=0; ListNode* rhead=head; while(head) { ++count; head=head->next; } count-=k; while(count) { rhead=rhead->next; --count; } return rhead; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

运行结果

提交代码（递归）

int count=0; ListNode* ans; void help(ListNode* head,int k) { if(head==NULL) return ; else { help(head->next,k); ++count; if(count==k) { ans=head; return ; } } } ListNode* getKthFromEnd(ListNode* head, int k) { help(head,k); return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

运行结果

提交代码（双指针）

ListNode* getKthFromEnd(ListNode* head, int k) { ListNode* slow=head; ListNode* fast=head; for(int i=0;i<k;++i) fast=fast->next; while(fast) { slow=slow->next; fast=fast->next; } return slow; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108624449