栈/队列 解法

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

然后从栈顶(队列头)弹出 个( 个)元素,最后一个出栈(出队列)的元素即是答案。

代码(栈):

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 先走 步,此时 fastslow 之间距离为 ,之后让 fastslow 指针一起走(始终维持相对距离为 ),当 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」中比较经典而又不过时的题目都讲一遍。

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

欢迎关注,交个朋友 (`・ω・´)