Leetcode-链表中倒数第k个节点

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流
作者简介:
CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
掘金LV3用户 https://juejin.cn/user/1381426159953960
阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目要求

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

方法1：统计长度

思路

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

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

代码

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* cur = pListHead;
    //统计链表长度
    int size = 0;
    while(cur)
    {
        cur = cur->next;
        size++;
    }
    //如果k大于链表长度，不可能找到
    if(k > size)
    {
        return NULL;
    }
    
    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;
 * };
 */

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