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

有空一起学习 2020年2月9日19:22:16 发表评论
文章最后编辑于:2020-2-9 19:24:30

一、题目

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

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

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

二、解题思路

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

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

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

fast指针先往前走三步:

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

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

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

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

三、代码

代码中需要注意的问题:

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

四、单元测试

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

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

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

 

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

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

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

测试结果:

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

本文共执行69次查询,耗时0.618秒!
历史上的今天
二月
9
有空一起学习

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: