【数据结构与算法面试题】单向链表倒数第k个节点

旧城等待， 2022-10-07 03:52 125阅读 0赞

> 题目来源“[数据结构与算法面试题80道][80]”。

![这里写图片描述][7173876036f4dd64c7b2facce705078d.png]

问题分析：遍历一遍链表的时间复杂度为O(n)，但是链表节点的遍历只能按顺序遍历，问题中是需要取到倒数第k个，最直接的想法是遍历两遍链表，第1遍得到链表的长度，第2遍是取到倒数第k个；那么能否只遍历一遍就能取到倒数第k个节点，最关键的点是需要确定链表的长度，我们可以使用双指针的方法：第一个指针用于遍历整个链表，第二个链表用于遍历部分链表，第一个指针比第二个指针多走k步，当第一个指针遍历完链表，第二个指针所指的即为倒数第k个数，如下图所示：

![这里写图片描述][5efe56a327cd0fc7a3ea08e7b699682f.bmp]

方法：

ListNode* get_reverse_k(ListNode *head, int k){
        if (NULL == head) return NULL;
    
        ListNode *p = head;
        ListNode *q = head;
        int step = 0;
        while (NULL != p->m_pNext){
            if (step >= k){
                q = q->m_pNext;
            }
            p = p->m_pNext;
            step ++;
        }
        if (step < k) return NULL;
        else return q;
    }

[80]: https://yq.aliyun.com/articles/40478?utm_content=m_15768
[7173876036f4dd64c7b2facce705078d.png]: /images/20221005/bdb07ecaca484e2194dc667d3e823e0f.png
[5efe56a327cd0fc7a3ea08e7b699682f.bmp]: /images/20221005/cf0086c1a25041c6b5095728ee268c39.png

发表评论取消回复

表情：

评论列表（有 0 条评论，125人围观）

还没有评论，来说两句吧...

相关阅读

相关链表中倒数第k个节点

[https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&rp=1&ru=%2Ft

逃离我推掉我的手/ 2022年11月30日 04:17/ 0 赞/ 168 阅读

相关链表中倒数第 k 个节点

链表中倒数第 k 个节点 1、参考资料 https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kg

港控/mmm°/ 2022年11月29日 03:09/ 0 赞/ 170 阅读

相关链表中倒数第k个节点

链表中倒数第k个节点输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节

末蓝、/ 2022年11月22日 00:23/ 0 赞/ 167 阅读

相关【数据结构与算法面试题】单向链表倒数第k个节点

> 题目来源“[数据结构与算法面试题80道][80]”。 ![这里写图片描述][7173876036f4dd64c7b2facce705078d.png] 问题分析：遍历一

旧城等待，/ 2022年10月07日 03:52/ 0 赞/ 126 阅读

相关找出单向链表中倒数第k个节点的算法

有两种方式，使用递归和非递归算法一（非递归方式）：最简单的方式是从头开始遍历。算法二（递归方式）打印出第k个元素的值。 public static

小咪咪/ 2022年07月26日 00:05/ 0 赞/ 121 阅读

相关链表中倒数第k个节点

package cn.com.jianzhioffer; import java.util.List; public

╰+攻爆jí腚メ/ 2022年05月24日 04:59/ 0 赞/ 154 阅读

相关链表问题_链表中倒数第K个节点

题目：输入一个链表，输出该链表中倒数第k个节点。尾节点为倒数第一个节点。分析：可以采用两个指针，记为start和end，先让end在链表上走k-1步，然后两个节点同时开始

水深无声/ 2022年05月21日 01:41/ 0 赞/ 163 阅读

相关【题22 链表中倒数第k个节点】

> 代码的鲁棒性 > 鲁棒性： > 指程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理 > 提高鲁棒性方法：防御性编程 > 防御性编程：

谁践踏了优雅/ 2022年03月25日 01:52/ 0 赞/ 171 阅读

相关【数据结构】（循环链表）单链表查询倒数第k个节点方案

> 算法思想:定义两个指针p,q ,q先走k步,之后p,q同时移动 p所指向的即为所求 int Search_k(LinkList A,int k){

秒速五厘米/ 2021年10月30日 00:28/ 0 赞/ 204 阅读

相关链表之链表中倒数第k个节点

public class Solution { public ListNode FindKthToTail(ListNode head,int k) {

小鱼儿/ 2021年09月18日 04:54/ 0 赞/ 297 阅读