【链表中倒数最后k个节点~~~链表+双指针+快慢指针】

硕风和炜

于 2023-01-04 18:50:29 发布

阅读量110

点赞数 1

分类专栏： # 链表系列文章标签：链表数据结构 Java 双指针快慢指针

本文链接：https://blog.csdn.net/Coder_ljw/article/details/128552640

版权

链表系列专栏收录该内容

43 篇文章

订阅专栏

题目描述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。
在这里插入图片描述

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
在这里插入图片描述

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

求解思路&实现代码

改题目是一道链表的题目，通过双指针-快慢指针来求解。具体的求解思路代码都在实现代码中

import java.util.*;
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) { 
        int n = 0;
        ListNode fast = pHead;
        ListNode slow = pHead;
        //快指针先行k步 fast-template
        for(int i = 0; i < k; i++){
            if(fast != null)
                fast = fast.next;
            //达不到k步说明链表过短，没有倒数k
            else
                return slow = null;
        }
        //快慢指针同步，快指针先到底，慢指针指向倒数第k个
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;}
}