前言

本系列主要整理面试中需要掌握的手撕代码题。本节介绍链表倒数节点问题。

一、BM8 链表中倒数最后k个结点

（1）定义快慢指针，首先让快指针走k个位置；
（2）然后让快慢指针同时移动，当快指针到末尾的时候，慢指针的位置就是倒数第k个。

function FindKthToTail( pHead , k ) {
    
    // write code here
    var fast = pHead;
    var slow = pHead;
    for(var i=0;i<k;i++){
    
        if(fast==null){
    
            return null
        }
        fast = fast.next;
    }

    while(fast){
    
        fast = fast.next;
        slow = slow.next;
    }
    return slow
}

二、BM9 删除链表的倒数第n个节点

（1）首先用上题的方法找到需要删除的节点，注意的就是定位到需要删除的前一个节点；
（2）判断要删除的是否是第一个节点，如果是，直接返回头节点的next；
（3）如果不是，则将该节点的next的next赋值给next。

function removeNthFromEnd( head , n ) {
    
    // write code here
    var slow = head;
    var fast = head;
    for(var i=0;i<n;i++){
    
        if(fast == null){
    
            return head
        }
        fast = fast.next
    }
    if(fast == null){
    
        return head.next
    }
    while(fast.next!=null){
    
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next
    return head
}