【宫水三叶の剑指精选】一题三解 :「栈/队列」&「差值法」&「快慢指针」

栈/队列 解法

一个使用额外空间的解法是利用栈（队列），将所有的节点压入占中栈（队列）中，令当前栈（队列）容量为 。

然后从栈顶（队列头）弹出 个（ 个）元素，最后一个出栈（出队列）的元素即是答案。

代码（栈）：

import java.util.*;

public class Solution {
    public ListNode FindKthToTail (ListNode head, int k) {
        Deque<ListNode> d = new ArrayDeque<>();
        while (head != null) {
            d.addLast(head);
            head = head.next;
        }
        if (d.size() < k) return null;
        ListNode ans = null;
        while (k-- > 0) ans = d.pollLast();
        return ans;
    }
}

代码（队列）：

import java.util.*;

public class Solution {
    public ListNode FindKthToTail (ListNode head, int k) {
        Deque<ListNode> d = new ArrayDeque<>();
        while (head != null) {
            d.addLast(head);
            head = head.next;
        }
        if (d.size() < k) return null;
        k = d.size() - k + 1;
        ListNode ans = null;
        while (k-- > 0) ans = d.pollFirst();
        return ans;
    }
}

• 时间复杂度：
• 空间复杂度：

差值法

我们可以先对链表进行一次完整遍历，拿到总长度 ，最后由 即是倒数第 个节点距离 节点的距离。

代码：

import java.util.*;

public class Solution {
    public ListNode FindKthToTail (ListNode head, int k) {
        int cnt = 0;
        ListNode tmp = head;
        while (tmp != null && ++cnt > 0) tmp = tmp.next;
        if (cnt < k) return null;
        cnt -= k;
        while (cnt-- > 0) head = head.next;
        return head; 
    }
}

• 时间复杂度：
• 空间复杂度：

快慢指针

事实上，我们还可以使用「快慢指针」进行求解。

起始先让快指针 fast 先走 步，此时 fast 和 slow 之间距离为 ，之后让 fast 和 slow 指针一起走（始终维持相对距离为 ），当 fast 到达链表尾部，slow 即停在倒数第 个节点处。

代码：

import java.util.*;

public class Solution {
    public ListNode FindKthToTail (ListNode head, int k) {
        ListNode slow = head, fast = head;
        while (k-- > 0 && fast != null) fast = fast.next;
        if (k != -1) return null;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

• 时间复杂度：
• 空间复杂度：

最后

这是我们「剑指 の 精选」系列文章的第 No.69 篇，系列开始于 2021/07/01。

该系列会将牛客网「剑指 Offer」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)