链表中关于快慢指针的oj题

题目一：

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

leetcode链接：力扣
 

解题思路：设定两个指针，一个是快指针，一个是慢指针。保持快指针的速度是慢指针的两倍，这样当快指针走到末尾的时候，慢指针刚好走到中间。返回慢指针。

如图：

 需要注意的是分奇偶讨论，while循环结束的条件有所不同。

代码：

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
struct ListNode*slow=head,*fast=head;

while(fast&&fast->next)
{
    slow=slow->next;
    fast=fast->next->next;
}
return slow;
    }
};

题目二：求倒数第k个结点

题目描述：

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

leetcode链接：链表中倒数第k个结点_牛客题霸_牛客网

思路：由于是求倒数第k个结点，因此就是求从尾结点开始倒数k-1步数的那个结点。可以定义两个指针。一个指针先走k-1步，另一个指针再开始走。等先走的指针走到了尾结点的时候，返回另一个指针就是要求得结点。

如图：

代码：

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    ListNode*slow=pListHead;
    ListNode*fast=pListHead;
        while(--k)//走k-1步
        {if(fast==NULL)
            return NULL;
         //如果k大于链表的长度 直接返回空
            fast=fast->next;
        }
        while(fast->next)//fast走到null结束
        {
            fast=fast->next;
            slow=slow->next;
        }
        
        return slow;
        
    }
};