[数据结构与算法]【算法面试必刷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;
}

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