写点什么

算法题学习 --- 链表中倒数最后 k 个结点

作者:桑榆
  • 2022-11-12
    广东
  • 本文字数:1731 字

    阅读完需:约 6 分钟

题目

描述

输入一个长度为 n 的链表,设链表中的元素的值为 a(i) ,返回该链表中倒数第 k 个节点。

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

数据范围:0≤n≤10^5,0≤ai≤10^9,0≤k≤10^9

要求:空间复杂度 O(n),时间复杂度 O(n)

进阶:空间复杂度 O(1),时间复杂度 O(n)

例如输入{1,2,3,4,5},2 时,对应的链表结构如下图所示:

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

示例 1

输入:{1,2,3,4,5},2返回值:{4,5}说明:返回倒数第2个节点4,系统会打印后面所有的节点来比较。 
复制代码

示例 2

输入:{2},8返回值:{}
复制代码

分析

考虑特殊情况

在进行问题分析过程前,我们先考虑一下特殊情况,那么在这道问题中,有哪些情况是特殊的呢?

不难发现,如下情况:

  • 如果输入的头结点为空,那么返回 nullptr 即可

考虑一般情况

第一种方法---遍历得到链表长度

这种方法是比较容易想到的,我们先遍历一次链表,计算出链表长度 length,要找出倒数第 k 个节点,那么我们只需要正向走 length-k 步就好。需要遍历两次链表,使用的空间和时间也是符合要求的。

第二种方法---双指针法

从第一个方法中得到启示,我们需要知道怎么才能走 length-k 步,这样考虑,我们设置快慢指针,快指针先走 k 步,然后慢指针再和快指针一起走,这样,当快指针走到链表末尾时,慢指针恰好走了 length-k 步,也就直接返回慢指针的节点就好了。

  • step 1:准备一个快指针,从链表头开始,在链表上先走 k 步。

  • step 2:准备慢指针指向原始链表头,代表当前元素,则慢指针与快指针之间的距离一直都是 k

  • step 3:快慢指针同步移动,当快指针到达链表尾部的时候,慢指针正好到了倒数 k 个元素的位置。

代码示例

版本一

先计算链表长度 length,然后使用 pCur 进行 length-k 次遍历。

注意,如果得出的长度小于 k,会直接返回 nullptr

/** * struct ListNode { *        int val; *        struct ListNode *next; *        ListNode(int x) : val(x), next(nullptr) {} * }; */class Solution {public:    /**     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可     *     *      * @param pHead ListNode类      * @param k int整型      * @return ListNode类     */    ListNode* FindKthToTail(ListNode* pHead, int k) {        // write code here        if(nullptr == pHead){            return pHead;        }
int length = 0; ListNode* pCur = pHead; while(nullptr != pCur){ length++; pCur = pCur->next; } if(length < k){ return nullptr; }
pCur = pHead; for(int i = 0; i < length-k;++i){ pCur = pCur->next; }
return pCur; }};
复制代码

版本二

使用快慢两个指针,快指针先走 K 步(走不到 K 步就空指针说明长度不够,也返回 nullptr);然后快慢指针同步走,最后快指针走到末尾,慢指针正好走到倒数第 k 个位置。

/** * struct ListNode { *  int val; *  struct ListNode *next; *  ListNode(int x) : val(x), next(nullptr) {} * }; */class Solution {  public:    /**     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可     *     *     * @param pHead ListNode类     * @param k int整型     * @return ListNode类     */    ListNode* FindKthToTail(ListNode* pHead, int k) {        // write code here        if (nullptr == pHead) {            return pHead;        }
ListNode* pQuick = pHead; ListNode* pSlow = pHead;
//pQuick walk k step for (int i = 0; i < k; ++i) { if (nullptr == pQuick) { return pQuick; } pQuick = pQuick->next; }
//pQuick and pSlow walk together while (nullptr != pQuick) { pQuick = pQuick->next; pSlow = pSlow->next; } return pSlow; }};
复制代码


发布于: 刚刚阅读数: 4
用户头像

桑榆

关注

北海虽赊,扶摇可接;东隅已逝,桑榆非晚! 2020-02-29 加入

Android手机厂商-相机软件系统工程师 爬山/徒步/Coding

评论

发布
暂无评论
算法题学习---链表中倒数最后k个结点_算法题_桑榆_InfoQ写作社区