一、题目
- 输入一个单向链表，输出该链表中倒数第
k个节点。为了符合大多数人的习惯，本题从1开始计数，即：链表的尾节点是倒数第1个节点。 - 例如，一个链表有
6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
二、示例
2.1> 示例：
【输入】给定一个链表: 1->2->3->4->5, 和 k = 2.
【输出】返回链表 4->5.
三、解题思路
- 根据题意，我们可以获得一个单向链表，那么要求根据题目给出的
k值来获取倒数第k个节点并返回该节点。那么因为单向链表只能向后遍历，并且对于单向链表我们除非遍历到尾节点，否则也不知道这个单向链表长度是多少。那么，如果要获得倒数第k个节点，就需要我们采用某种可以回退回去的办法，即：回退的方向与遍历的方向相反。 - 那么既然需要回退回去，我们就可以通过递归的方式来对这道题进行解答，即：通过递归的方式遍历链表，当发现某个节点node的next节点为null，则表明已经遍历到了最后一个节点。那么我们就直接return即可。这样，就可以回退到前一个节点了。那么，当满足回退到倒数第k个节点的时候，我们将该节点return返回即可。
- 下面我们以链表
1—>2—>3—>4—>5—>6，要找到k=4的节点为例，具体操作过程请见下图所示：
四、代码实现
classSolution { intnum=0; publicListNodegetKthFromEnd(ListNodehead, intk) { if (head==null) returnnull; ListNodenode=getKthFromEnd(head.next, k); if (++num==k) returnhead; returnnode; } } /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
