page contents
首页 问答
正文

如何找出单链表中的倒数第k个元素？

轩辕小不懂 发布于 2022-03-24 16:27
阅读 484
收藏 0
答案 1
分类：人工智能
  • 人工智能
  • python
  • 编程论坛

    • 找出单链表中的倒数第k个元素，例如给定单链表：1-＞2-＞3-＞4-＞5-＞6-＞7，则单链表的倒数第k=3个元素为5。

    默认排序 时间排序
    3368
    Nen
    Nen
    - 程序员

    方法一：顺序遍历两遍法主要思路：首先遍历一遍单链表，求出整个单链表的长度n，然后把求倒数第k个元素转换为求顺数第n-k个元素，再去遍历一次单链表就可以得到结果。但是该方法需要对单链表进行两次遍历。

    方法二：快慢指针法由于单链表只能从头到尾依次访问链表的各个结点，因此，如果要找链表的倒数第k个元素，也只能从头到尾进行遍历查找，在查找过程中，设置两个指针，让其中一个指针比另一个指针先前移k步，然后两个指针同时往前移动。循环直到先行的指针值为None时，另一个指针所指的位置就是所要找的位置。

    请先 登录 后评论
    轩辕小不懂
    1 关注
     
    轩辕小不懂
    提出于 2022-03-24 16:27
    全部

    轩辕小不懂 的其他提问

    类似问题

    运行时异常与一般异常有何异同？
    1 回答
    484 阅读
    String 和StringBuffer的区别？
    2 回答
    484 阅读
    怎样将字符串中第一个字母大写？
    3 回答
    484 阅读
    在Python中如何生成一个随机数？
    1 回答
    484 阅读
    Python中的不可变集合（frozenset）是什么？
    1 回答
    484 阅读
    在Python中怎样获取输入？
    1 回答
    484 阅读