图解LeetCode——剑指 Offer 22. 链表中倒数第k个节点

一、题目

• 输入一个单向链表，输出该链表中倒数第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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。