【算法面试必刷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)
 */publicListNodeFindKthToTail1(ListNode pHead,int k){Deque<ListNode> deque =newArrayDeque<>(k);ListNode cur = pHead;while(k-->0){if(cur ==null){returnnull;}
        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)
 */publicListNodeFindKthToTail(ListNode pHead,int k){// write code hereListNode cur = pHead;ListNode result = pHead;while(k-->0){if(cur ==null){returnnull;}
        cur = cur.next;}while(cur !=null){
        cur = cur.next;
        result = result.next;}return result;}

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