实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：
给定的 k 保证是有效的。
这个题是非常简单的，大家看到题目可以先自己想想怎么做，然后再看题解！
这题其实是非常经典的用快慢指针解决的问题，大概思路是： 快指针先走k步，然后快慢指针同时往前走，直到快指针到结尾的时候，返回慢指针节点的值。
看代码实现：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int kthToLast(ListNode head, int k) { ListNode fast=head; ListNode slow=head; for(int i=1;i fast=fast.next; } while(fast.next!=null){ fast=fast.next; slow=slow.next; } return slow.val; } } 我以为自己已经很牛了，但是看了力友的解题我又跪了！ 以下解题来自：lc大佬 方法二：使用栈解决 把原链表的结点全部压栈，然后再把栈中最上面的k个节点出栈，出栈的结点重新串成一个新的链表即可，直接看下代码： public int kthToLast(ListNode head, int k) { Stack stack = new Stack<>(); //链表节点压栈 while (head != null) { stack.push(head); head = head.next; } //在出栈串成新的链表 ListNode firstNode = stack.pop(); while (--k > 0) { ListNode temp = stack.pop(); temp.next = firstNode; firstNode = temp; } return firstNode.val; } 方法三：递归求解 终止条件很明显就是当节点head为空的时候，就没法递归了，这里主要看的是逻辑处理部分，当递归往下传递到最底端的时候，就会触底反弹往回走，在往回走的过程中记录下走过的节点，当达到k的时候，说明到达的那个节点就是倒数第k个节点，直接返回即可。接下来直接看代码： //全局变量，记录递归往回走的时候访问的结点数量 int size; public int kthToLast(ListNode head, int k) { //边界条件判断 if (head == null) return 0; int val = kthToLast(head.next, k); ++size; //从后面数结点数小于k，返回空 if (size < k) { return 0; } else if (size == k) { //从后面数访问结点等于k，直接返回传递的结点k即可 return head.val; } else { //从后面数访问的结点大于k，说明我们已经找到了， //直接返回node即可 return val; } }
这里在总结一下递归算法吧！！
递归算法就是一个先递后归的过程，在这个题中图解如下：
把这个题的递归方法抽取一下精华就是：
public ListNode getKthFromEnd(ListNode head, int k) { //终止条件 if (head == null) return head; //递归调用 ListNode node = getKthFromEnd(head.next, k); //逻辑处理 …… }
1.有递归调用
2.有递归出口
3.使用递归的逻辑的处理
大家有什么问题欢迎私聊探讨！
