LeetCode刷题【剑指 Offer 22】链表中倒数第k个节点

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

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

示例：

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

返回链表 4->5.

题解

9月2日每日一题，最常规的解法应该声明一个数组，然后就是遍历链表，记录下每个节点，最后得到总长之后，到数组中找到总长减去k位置的并返回

我这边的第一反应是递归，探底后返回依次加1，加到k的时候记录下这倒数第k个结点。原理类似DFS的后序遍历。

class Solution {
    int k = 0;
    int count = 0;
    ListNode node;
    public ListNode getKthFromEnd(ListNode head, int k) {
        this.k = k;
        func(head);
        return node;
    }


    public void func(ListNode head){
        if (head == null){
            return;
        }
        func(head.next);
        count++;
        if (count == k){
            node = head;
        }
    }
}

另外的一种，双指针，如下，具体思路逻辑详见注释

class Solution {
    ListNode node1;
    ListNode node2;
    public ListNode getKthFromEnd(ListNode head, int k) {
        node1 = head;
        node2 = head;
        //这里初始为1，举例说明 链表【1,2,3】，倒是第一个应当是3，不存在倒数第0个的这种说法
        int count = 1;
        //让node2先跑k步
        while (node2.next != null && count<k){
            node2 = node2.next;
            count++;
        }
        if (count < k){
            //假如链表总长度小于k
            return null;
        }
        //此时node2在node1后面距离k,接下来，node1和node2一起往后跑
        //当node2跑到结尾的时候，node1即为倒数第k个了
        while (node2.next != null){
            node1 = node1.next;
            node2 = node2.next;
        }

        return node1;
    }
}

当然这边也可以再优化下，写到一个while循环里，通过条件判断让node2先跑k个，双指针的思路和上次LeetCode刷题【876】链表的中间结点有点类似，都是通过控制两个指针之间的相对距离，找出链表中间的某个节点。