431，剑指 Offer-链表中倒数第k个节点

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #剑指offer 34个

Every passing minute is another chance to turn it all around.

过去的每一分钟都是改变现状的一次机会。

问题描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

双指针求解

这题要求链表的倒数第k个节点，最简单的方式就是使用两个指针，第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可。

 1public ListNode getKthFromEnd(ListNode head, int k) {
 2    ListNode first = head;
 3    ListNode second = head;
 4    //第一个指针先走k步
 5    while (k-- > 0) {
 6        first = first.next;
 7    }
 8    //然后两个指针在同时前进
 9    while (first != null) {
10        first = first.next;
11        second = second.next;
12    }
13    return second;
14}

使用栈解决

这题要求的是返回后面的k个节点，我们只要把原链表的结点全部压栈，然后再把栈中最上面的k个节点出栈，出栈的结点重新串成一个新的链表即可，原理也比较简单，直接看下代码。

 1public ListNode getKthFromEnd(ListNode head, int k) {
 2    Stack<ListNode> stack = new Stack<>();
 3    //链表节点压栈
 4    while (head != null) {
 5        stack.push(head);
 6        head = head.next;
 7    }
 8    //在出栈串成新的链表
 9    ListNode firstNode = stack.pop();
10    while (--k > 0) {
11        ListNode temp = stack.pop();
12        temp.next = firstNode;
13        firstNode = temp;
14    }
15    return firstNode;
16}

递归求解

我们之前讲过链表的逆序打印410，剑指 Offer-从尾到头打印链表，其中有这样一段代码

1public void reversePrint(ListNode head) {
2    if (head == null)
3        return;
4    reversePrint(head.next);
5    System.out.println(head.val);
6}

这段代码其实很简单，我们要理解他就要弄懂递归的原理，递归分为两个过程，递和归，看一下下面的图就知道了，先往下传递，当遇到终止条件的时候开始往回走。

前面也刚讲过递归的原理426，什么是递归，通过这篇文章，让你彻底搞懂递归，这题如果使用递归的话，我们先来看一下递归的模板

1public ListNode getKthFromEnd(ListNode head, int k) {
2    //终止条件
3    if (head == null)
4        return head;
5    //递归调用
6    ListNode node = getKthFromEnd(head.next, k);
7    //逻辑处理
8    ……
9}

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

 1//全局变量，记录递归往回走的时候访问的结点数量
 2int size;
 3
 4public ListNode getKthFromEnd(ListNode head, int k) {
 5    //边界条件判断
 6    if (head == null)
 7        return head;
 8    ListNode node = getKthFromEnd(head.next, k);
 9    ++size;
10    //从后面数结点数小于k，返回空
11    if (size < k) {
12        return null;
13    } else if (size == k) {
14        //从后面数访问结点等于k，直接返回传递的结点k即可
15        return head;
16    } else {
17        //从后面数访问的结点大于k，说明我们已经找到了，
18        //直接返回node即可
19        return node;
20    }
21}

上面代码在仔细一看，当size小于k的时候node节点就是空，所以我们可以把size大于k和小于k合并为一个，这样代码会更简洁一些

 1int size;
 2
 3public ListNode getKthFromEnd(ListNode head, int k) {
 4    if (head == null)
 5        return head;
 6    ListNode node = getKthFromEnd(head.next, k);
 7    if (++size == k)
 8        return head;
 9    return node;
10}