《剑指offer》面试题22:链表中的倒数第k个节点

马谦马谦马谦 数据结构和算法评论198字数 662阅读2分12秒阅读模式

一、题目

输入一个链表,输出该链表中倒数第k个节点,为了符合大多数人的习惯,k的序号从1开始,即链表的尾结点是倒数第一个节点。

例如,如下链表中的倒数第3个节点是3

《剑指offer》面试题22:链表中的倒数第k个节点-图片1

二、解题思路

使用快慢指针,快指针先走n步,然后快慢指针同时走,直到快指针为null,慢指针就是倒数第n个节点。

以上面的链表为例,初始时,两个指针都指向链表开头:

《剑指offer》面试题22:链表中的倒数第k个节点-图片2

fast指针先往前走三步:

《剑指offer》面试题22:链表中的倒数第k个节点-图片3

此时,fast和slow同时往前走,直到fast为空:

《剑指offer》面试题22:链表中的倒数第k个节点-图片4

此时slow所在的位置刚好就是倒数第三个节点。

三、代码

代码中需要注意的问题:

  1. 链表可能为空,避免空指针访问。
  2. 链表长度可能不够n,遍历fast的时候注意判断非空,并且外部应该判断出这一点。

四、单元测试

单元测试主要覆盖以下几点:

  1. 链表为空的场景。
  2. 链表不为空,获取倒数第1个节点。
  3. 链表不为空,获取倒数第n个节点,n等于链表长度。
  4. 链表不为空,获取倒数第n个节点,n大于链表长度。

TestFixtures定义了三个链表,第一个链表有5个元素,第二个链表为空,第三个链表有1个元素。

 

测试案例一:获取倒数第n个节点,n分别大于、小于和等于链表长度。

测试案例二:测试空链表。

测试案例三:只有一个节点的链表测试。

测试结果:

《剑指offer》面试题22:链表中的倒数第k个节点-图片5

 
马谦马谦马谦
  • 本文由 马谦马谦马谦 发表于 2020年2月9日19:22:16
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/find-nth-node-from-end-of-list.html
redis源码分析:链表实现 Redis

redis源码分析:链表实现

一、链表定义 链表在redis中的使用十分广泛,例如列表的底层实现之一就是链表,包括发布、订阅等等功能都是有用到链表的。redis中链表在adlist.h和adlist.c中实现,只用了300+行代码...
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证