舍友仅仅上了个厕所，我就求出了链表的倒数第K个结点

文章目录

题目要求

链接 :链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

本题目和博主曾经写过的：是一样的套路！感兴趣的老铁可以翻过去看一下！
舍友仅仅打了一把游戏，我就学会了如何找链表的中间结点

方法1：统计长度

思路

• 第一步：遍历链表得出链表的长度，记为size，如果k大于链表的长度，不可能找到 。返回NULL
• 第二步：从头开始走 size - k 步，就是倒数的第K个结点

从头开始走：倒数第K个结点的位置是正数的第size-k位置

代码

structListNode*FindKthToTail(structListNode* pListHead,int k ){structListNode* cur = pListHead;//统计链表长度int size =0;while(cur){
        cur = cur->next;
        size++;}//如果k大于链表长度，不可能找到if(k > size){returnNULL;}int n = size-k;//倒数第K个结点的位置是正数的第size-k位置//从头开始走n步
    cur = pListHead;//cur走n步while(n--){
      cur = cur->next;}return cur;}

方法2：双指针

思路

• 第一步：fast指针先走K步- ==注意：==如果走k步时：fast走到了NULL，说明k是比链表的长度大的，此时不可能找到倒数第K个结点 ->返回NULL

while(k--)==>循环k次 ->走k步
while(--k)==>循环k-1次 ->走k-1步

• 第二步：fast和slow一起走，当fast走到NULL时，slow就是倒数第K个结点（奇数个结点个或者偶数个结点都可以）

图解

代码

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */structListNode*FindKthToTail(structListNode* pListHead,int k ){// write code here//定义双指针structListNode* fast = pListHead;structListNode* slow = pListHead;//fast 先走K步while(k--){//k的大小大于链表长度， fast提前走到空if(fast ==NULL){returnNULL;}
        fast = fast->next;}//fast和slow一起走//当fast走到NULL 此时slow就是倒数的第K个结点while(fast){
        fast = fast->next;
        slow = slow->next;}return slow;}