JZ14-链表中倒数最后k个结点(双指针、链表)

描述

输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

示例1

输入：

{1,2,3,4,5},1 

返回值：

{5}

解题思路

要输出倒数第k个到尾节点的全部节点

这两个节点之间相差k个

而双指针可以解决这个问题

快指针先出发，如果不足k次移动就到结尾直接返回空

之后慢指针出发，到快指针指即将指向空时结束

返回慢指针即可

其中的麻烦点就在于边界条件，特别需要注意k与链表长度相等时以及链表本身为空

代码

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
function FindKthToTail( pHead ,  k ) {
    // write code here
    let fast=pHead;
    let slow = pHead;
    if(!pHead){  //注意
        return null
    }
    
    while(--k){ //注意--k,若是k--可能长度相等时直接返回空
        fast = fast.next;
        if(fast==null){
            return fast;
        }
    }
    
    while(fast.next!=null){
        slow = slow.next;
        fast = fast.next;
    }
    return slow
    
}
module.exports = {
    FindKthToTail : FindKthToTail
};

遇事不决，画图解决