[牛客]链表中倒数第k个结点

牛客链接

使用快慢指针法:

两种思路:

1.fast先向后走k-1次,slow再向后走1次,然后fast和slow同时向后走,当fast走到最后一个结点时,slow刚好在倒数第k个位置上;

2.fast先向后走k次,slow再向后走1次,然后fast和slow同时向后走,当fast走到最后一个结点的后面时(此时为NULL),slow刚好在倒数第k个位置上;

根据这个思路,我们可以写出初始代码如下:

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */


/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
   
   struct ListNode* fast,*slow;
   fast = slow = pListHead;
   while(k--)//循环k次
   {
     
    fast = fast->next;//fast向后走k次
   
   }
   while(fast)//当fast为空时,slow指向倒数第k个结点
   {
    slow = slow->next;//不为空,同时向后走
    fast = fast->next;


   }
   
   return slow;
}

需要注意代码中while(k--)是循环k次,而while(--k)是循环k-1次.

这样看,代码似乎没什么问题,但是运行之后报了错:

这时我们需要通过测试用例来进行分析

通过第三个用例,我们可以考虑到链表为空的情况

通过第四个用例,考虑到k多于链表结点数时的情况

进行逻辑分析和修改后的代码如下:

正确代码

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */


/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    if(pListHead == NULL)//链表为空
    {
        return NULL;
    }
   struct ListNode* fast,*slow;
   fast = slow = pListHead;
   while(k--)
   {
     if(fast== NULL)//当k>链表结点数时
    {
        return NULL;
    }
    fast = fast->next;
   
   }
   while(fast)
   {
    slow = slow->next;
    fast = fast->next;


   }
   
   return slow;
}

需要注意的是代码中的if(fast == NULL)语句必须放在fast = fast->next;之前,原因可自行分析

结语：

这里本章内容就介绍完了，文章中某些内容我们之前有介绍，所以只是一笔带过，还请谅解。

希望以上内容对大家有所帮助