链表中倒数最后k个结点

题目描述

示例

示例1

输入：
{1,2,3,4,5},2
返回值：
{4,5}
说明：
返回倒数第2个节点4，系统会打印后面所有的节点来比较。

示例2

输入：
{2},8
返回值：
{}

代码

代码1 快慢指针法

/*
快慢指针法（快慢指针都先指向一个虚拟的头节点）
1. 快指针先走k步，走到k步之后，慢指针开始走
2. 快指针走到null，结束
    此时，慢指针走的位置即为结果，
    如果快指针走到null了，慢指针还没开始走，就说明范围超了
*/
function FindKthToTail( pHead ,  k ) {

    let vHead = new ListNode(-1) // 虚拟头结点
    vHead.next = pHead
    
    let fast = vHead // 快指针
    let slow = vHead // 慢指针
    
    // 快指针先走K步，慢指针开始走
    let count = 0 // 计步器
    
    while(fast){
        if(count >= k){ // 慢指针开始走
            slow = slow.next
        }
        fast = fast.next
        count++
    }
    // 如果慢指针一步没走，就说明K太大了
    if(slow === vHead) return null
    return slow
}

代码2 使用栈

/*
使用栈
1. 先把链表遍历一个遍，进栈
2. 然后出栈找到第K个节点
*/
function FindKthToTail( pHead ,  k ) {
    // 如果没有传或者k为0，直接返回null
    if(!pHead || k === 0){
        return null
    }
    
    let stack = [] // 模拟一个栈
    
    while(pHead){ // 全部进栈
        stack.push(pHead)
        pHead = pHead.next
    }
    
    // 如果k比数组长度还长 直接返回null
    if( k > stack.length ) return null
    
    // 开始找到倒数第k个节点
    let newHead = null
    while( k > 0 ){
        newHead = stack.pop()
        k--
    }
    
    return newHead
}

题目来源

JZ22 链表中倒数最后k个结点