题目链接

示例

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

解题思路

自己的思路：
压栈，然后循环K次出栈

大佬：
定义双指针，都在head处
先将前指针移动K个位置
此时，后指针在head处，前指针在第K节点处
然后同时移动两个指针，使它们始终保持间隔K个位置
当前指针为空时，说明后指针移动到了倒数第K个节点的位置

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        /*
        输出链表第K个节点
        链表的尾节点是倒数第一个节点
        */
        //自己想到的，压栈，出栈
        /*
        Deque<ListNode> stack1 = new LinkedList<>();;
        ListNode node = head;
        while(node!=null){
            stack1.push(node);
            node = node.next;
        }
        ListNode res = null;
        for(int i=0;i<k;i++){
            res = stack1.pop();
        }
        return res;
        */
        /*
        定义双指针，都在head处
        先将前指针移动K个位置
        此时，后指针在head处，前指针在第K节点处
        然后同时移动两个指针，使它们始终保持间隔K个位置
        当前指针为空时，说明后指针移动到了倒数第K个节点的位置
        */
        ListNode former = head, latter = head;
        for(int i = 0; i < k; i++)
            former = former.next;
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}