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

题目介绍

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

题目解析

从倒数第 N 个开始截断链表。链表结构如下所示，因为是单向链表不能从末尾开始遍历。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 *

第一次

暴力解法，保存节点生成下标，因为链表长度不可知，创建额外使用 List 保存节点，拥有空间开销

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) return null;
        List<ListNode> nodes = new ArrayList<>();
        ListNode node = head;
        while (node != null) {
            nodes.add(node);
            node = node.next;
        }
        int index = nodes.size() - k;
        return index >= 0 ? nodes.get(index) : null;
    }
}

第二次

利用栈的特性，https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci/

class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode node = head;
        Stack<ListNode> stack = new Stack<>();
        while(node != null) {
            stack.push(node);
            node = node.next;
        }
        while(!stack.isEmpty()) {
            node = stack.pop();
            if (k == 1) return node.val;
            k--;
        }

        return head.val;
    }

}

第三次

快慢指针法，Fast 指针先行 k 步，随后 Slow 指针开始前进，当 Fast 指针进行到尾部时，此时 Slow 指针即目标位置。

参考 Leetcode 用户，算法较为精巧一次遍历 O(n)，简化了 Slow 指针，但是请注意这里改变了原链表，如果题目有要求要初始化 Slow 指针。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) return null;
        ListNode fast = head;
        while (fast != null) {
            fast = fast.next;
            if(k == 0) {
                head = head.next;
            } else {
                k--;
            }
        }
        return head;
    }
}