剑指 Offer 22. 链表中倒数第k个节点 JavaScript实现

剑指 Offer 22. 链表中倒数第k个节点

题目链接

1、差值法

注意事项：
1、head就是整个链表的头节点，所以最后返回指定链表的头节点。
2、如果不使用新的指针去遍历链表，那么会造成遍历一遍链表之后，head到了末尾。
3、没有涉及到删除节点，只是原来的链表上返回一部分，所以不需要哑节点。

var getKthFromEnd = function(head, k) {
    // 第一次遍历，得到长度。
    let cur=head,n=0;
    while(cur){
        cur = cur.next;
        n++;
    }

    // 再一次遍历链表,只需将head指针移动到倒数第k个节点即可。
    for(let i=1;i<n-k+1;i++){
        head = head.next;
    }
    return head; 
};

2、栈

思想同19、删除链表的倒数第N个结点
不同点：
22.：只需要得到指向倒数第k个结点的指针，所以最后得到的是倒数第k个结点。
19：删除结点需要知道前驱结点，所以需要得到倒数第k个节点的前一个结点。需要删除结点，所以避免头节点删除的情况，添加了哑结点。

var getKthFromEnd = function(head, k) {
    let stack = [];
    while(head){
        // 存入的是节点的地址，并不是值
        stack.push(head);
        head = head.next;
    }
    
    // d出k之后的所有元素
    for(let i=1;i<k;i++){
        stack.pop();
    }

    // 再d出一个元素，就是倒数第k个元素。返回指向它的指针即可。也就是新链的头节点。
    let node = stack.pop()
    return node;
};