【算法面试必刷Java版八】链表中倒数最后k个结点

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

    

🚴🏻‍♂️个人主页：莫逸风

    

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

    

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：链表中倒数最后k个结点

描述：

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：0≤n≤105，0 ≤ai≤109，0 0≤k≤109

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

思路一：辅助队列

这里我使用的是Deque，Java中的一个双端队列。我们只需要迭代链表放入队尾，取出队头，保证队列中有k个元素，遍历结束后，队头元素即为倒数第k个元素。

思路二：双指针

定义cur指针指向第k个元素，result指向队头，然后同步遍历，当cur走到队尾，result即为倒数第k个元素。

思路三：反转链表

反转链表后，从头遍历。

代码：

/**
 * 栈，时间复杂度O(n),空间复杂度O(1)
 */
public ListNode FindKthToTail1(ListNode pHead, int k) {
    Deque<ListNode> deque = new ArrayDeque<>(k);
    ListNode cur = pHead;
    while (k-- > 0) {
        if (cur == null) {
            return null;
        }
        deque.add(cur);
        cur = cur.next;
    }
    while (cur != null && !deque.isEmpty()) {
        deque.pollFirst();
        deque.add(cur);
        cur = cur.next;
    }
    return deque.pollFirst();
}

/**
 * 迭代，时间复杂度O(n),空间复杂度O(1)
 */
public ListNode FindKthToTail(ListNode pHead, int k) {
    // write code here
    ListNode cur = pHead;
    ListNode result = pHead;
    while (k-- > 0) {
        if (cur == null) {
            return null;
        }
        cur = cur.next;
    }
    while (cur != null) {
        cur = cur.next;
        result = result.next;
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101