递归解法

image.png

终止条件很明显就是当节点head为空的时候，就没法递归了，这里主要看的是逻辑处理部分，当递归往下传递到最底端的时候，就会触底反弹往回走，在往回走的过程中记录下走过的节点，当达到k的时候，说明到达的那个节点就是倒数第k个节点，直接返回即可

往下深入的过程中，count = 0始终为0

然后当进入到head.next = null 的时候，那么开始触底反弹，

当count = k 的时候 用全局变量记录下来那个节点即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    int count = 0;
    ListNode resultNode = null;
    public ListNode getKthFromEnd(ListNode head, int k) {
        getKthFromEndRecur(head, k);
        return resultNode;
    }
    public void getKthFromEndRecur(ListNode head, int k) {
        if (head == null) return;
        getKthFromEndRecur(head.next, k);
        count++;
        if (count == k) {
            resultNode = head;
        }
    }
}

数组的方法

• 使用一个数组把链表的每个节点保存起来
• 倒数第1个 返回 arr[arr.length - 1]
• 倒数第2个 返回 arr[arr.length - 2]
• 然后倒数第 K 个就是返回数组下标为（数组的长度 - K）的值。
• 也就是返回 arr[arr.length - 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) {
        ArrayList<ListNode>  nodeList = new ArrayList<>();
        ListNode tmpHead  = head;
        while(tmpHead != null) { // 用数组把节点都存下来。
            nodeList.add(tmpHead);
            tmpHead = tmpHead.next;
        }
        if (k > nodeList.size()) return null; // 防止k的取值出现大于链表长度的情况
        return nodeList.get(nodeList.size() - k); // 倒数第K个节点
    }
}