快慢指针解法

链表中倒数第k个结点

http://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a

假设链表长度为n,则可以将链表分成3部分:

  1. 起点 [1,1]
  2. 第二个结点到第n-k个结点 [2, n-k]
  3. 倒数第k个结点到第n个结点 [n-k+1, n]
    划分如图:
    图片说明

所以结点从起点开始走n-k-1+1 = n-k步就到达倒数第k个结点。
也就是要计算出n-k的长度。
那么根据输入的参数k,设置快慢指针可以达到目的
设置快慢指针,让两者指向第一个结点
然后,先让快指针从起点走k步,此时访问的表长为k+1个结点,所以剩下的结点加上链表尾后的空位置共有n-(k+1)+1 = n-k个结点;
然后,让快慢指针同步向前走,当快指针到达空位置,两个指针都走了n-k步,即慢指针到达倒数第k个结点

全部评论

相关推荐

伟大的烤冷面被普调:暨大✌🏻就是强
点赞 评论 收藏
分享
10-05 23:02
东北大学 Java
我说句实话啊:那时候看三个月培训班视频,随便做个项目背点八股,都能说3 40w是侮辱价
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务