链表中倒数最后k个结点

标签：结点 ListNode int fast 链表 len 倒数 指针

• 描述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。 如果该链表长度小于k，请返回一个长度为 0 的链表。     数据范围：0≤n≤10^5，0≤ai​≤10^9，0≤k≤10^9 要求：空间复杂度 O(n)，时间复杂度 O(n) 进阶：空间复杂度 O(1)，时间复杂度 O(n)   例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示： 其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。  

• 示例1

输入：{1,2,3,4,5},2 返回值：{4,5} 说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。  

• 示例2

输入：{2},8 返回值：{}  

• 算法思想

方法1： 先计算链表长度len,再正序寻找倒数第k个节点，即寻找第len-k+1个节点。 方法2： 双指针法。

1、准备一个快指针，从链表头开始，在链表上先走k步。

2、准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是k。

3、快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数k个元素的位置。

 

• 代码

 1 /**
 2  * struct ListNode {
 3  *  int val;
 4  *  struct ListNode *next;
 5  *  ListNode(int x) : val(x), next(nullptr) {}
 6  * };
 7  */
 8 class Solution {
 9   public:
10     /**
11      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
12      *
13      *
14      * @param pHead ListNode类
15      * @param k int整型
16      * @return ListNode类
17      */
18     ListNode* FindKthToTail(ListNode* pHead, int k) {
19         //方法一
20         //计算链表长度
21         // ListNode *p=pHead;
22         // int len=0;
23         // while(p){
24         //     len++;
25         //     p=p->next;
26         // }
27         // if(k>len) return nullptr;
28         // //寻找倒数第k个节点
29         // int n=len-k+1;
30         // p=pHead;
31         // for(int i=0;i<n-1;i++)
32         //     p=p->next;
33         // return p;
34 
35         //方法二
36         ListNode* fast = pHead;
37         ListNode* slow = pHead;
38         //快指针先行k步
39         for (int i = 0; i < k; i++) {
40             if (fast != nullptr)
41                 fast = fast->next;
42             //达不到k步说明链表过短，没有倒数k
43             else
44                 return nullptr;
45         }
46         //快慢指针同步，快指针先到底，慢指针指向倒数第k个
47         while(fast!=nullptr){
48             fast = fast->next;
49             slow = slow->next;
50         }
51         return slow;
52     }
53 };

 

 

 

标签：结点,ListNode,int,fast,链表,len,倒数,指针
From： https://www.cnblogs.com/yueshengd/p/17381413.html