链表OJ题(三)

1. 链表中倒数第k个结点

链接：链表中倒数第k个结点

描述：
输入一个链表，输出该链表中倒数第k个结点。

示例1:：

输入：
1,{1,2,3,4,5}
返回值：
{5}

思路1–两次遍历

和求链表的中间节点的方法一相似，为直接法。

要求链表的倒数第 k 个节点，那么就是删除链表正数第 len(链表长度) - k + 1 个节点。

举个例子，例如链表长度为 5，删除倒数第 2 个节点，就是删除链表正数第 4 个节点，推导出来就是第 len + 1 - k 个节点。
所以只要先算出链表长度，然后遍历到 len + 1 - k 个节点返回即可。

注意
1.在计算出链表总长度len<k或k<=0时，直接返回NULL。
2.传递的是空链表，直接返回NULL

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{struct ListNode*cur,*ans;cur=ans=pListHead;int len=0;while (cur) {cur=cur->next;len++;}if(k<=0||k>len)return NULL;for (int i=0; i<len-k; i++) {ans=ans->next;}return ans;
}

在这里插入图片描述

既然这道题目也可以用直接法，那么能否也适用于快慢指针？事实上可以，而且这道题的方法也很巧妙，接下来看思路2

思路2-快慢指针

在上一篇博客中我们也使用了快慢指针
给定一个快指针 fast 和一个慢指针 slow；我们要求链表倒数第 k 个节点，那么我们就先让快指针走 k 步；然后让 fast 和 slow 一起走，当 fast 走到空指针，这时 slow 为倒数第 k 个节点。
在这里插入图片描述

那么这里的原理是什么呢？
首先让 fast 走 k 步，让 fast 和 slow 的间隔为 k。链表的倒数第 k 个节点，就是正数 len + 1 - k 个节点，那么当 fast 走到空指针后，链表走完，那么现在 fast 走的距离就相当于链表的长度len + 1，fast 和 slow的间隔为 k ，那么现在的 slow 就为正数 len + 1 - k个节点，这时返回 slow就是倒数第 k 个节点。

注意：如果在 fast 走 k 步的过程中，fast 迭代为了空指针，这时直接返回空指针。

代码：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{struct ListNode* fast, *slow;fast = slow = pListHead;if (pListHead == NULL)return NULL;// fast 先走 k 步while (k--)//走k次，（--k）走k-1次{// 放置 fast 先走到空if (fast == NULL){return NULL;}fast = fast->next;}// 迭代while (fast){slow = slow->next;fast = fast->next;}return slow;
}