【C#刷题】| 作者 / Edison Zhou
我们来用之前学到的数据结构知识来刷《剑指Offer》的一些核心题目(精选了其中30+道题目),希望对你有帮助!本文题目为:链表的倒数第k个节点。
1题目介绍
题目:输入一个链表,输出该链表中倒数第k个结点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾结点是倒数第1个结点。例如一个链表有6个结点,从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。
链表的节点定义如下,这里使用的是C#来定义:
public class Node
{
public int Data { get; set; }
public Node Next { get; set; }
public Node(int data)
{
this.Data = data;
}
public Node(int data, Node next)
{
this.Data = data;
this.Next = next;
}
}
2解法1:不可行的常规解法
为了得到倒数第k个结点,很自然的想法是先走到链表的尾端,再从尾端回溯k步。当时,从链表结点的定义可以看出本题中的链表是单向链表,单向链表的结点只有从前往后的指针而没有从后往前的指针,因此这种思路行不通,它只适用于双向链表。
如果链表定义中有指向前一个节点的指针,那么此解法是可行的,我们可以修改链表定义:
public class Node
{
public int Data { get; set; }
// 指向后一个节点
public Node Next { get; set; }
// 指向前一个节点Prev
public Node Prev { get; set; }
public Node(int data)
{
this.Data = data;
}
}
3解法2:可行但不高效的常规解法
假设整个链表有n个结点,那么倒数第k个结点就是从头结点开始的第n-k+1个结点。如果我们能够得到链表中结点的个数n,那我们只要从头结点开始往后走n-k+1步就可以了。
那么,这里的重点就在于如何求链表中节点的个数n,只需要从头开始遍历链表,每经过一个结点,计数器加1就行了。
但是,问题来了:这种思路需要遍历链表两次,第一次统计出链表中结点的个数,第二次才能找到倒数第k个结点。
4解法3:可行而且高效的解法
为了能够只遍历一次就能找到倒数第k个节点,可以定义两个指针:
(1)第一个指针从链表的头指针开始遍历向前走k-1,第二个指针保持不动;
(2)从第k步开始,第二个指针也开始从链表的头指针开始遍历;
(3)由于两个指针的距离保持在k-1,当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针正好是倒数第k个结点。
下图展示了在有6个结点的链表上找倒数第3个结点的过程:
画外音:当我们用一个指针遍历链表不能解决问题的时候,可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些(比如一次在链表上走两步),或者让它先在链表上走若干步。
(1)代码实现
public static Node FindKthToTail(Node head, uint k)
{
Node ahead = head;
Node behind = null;
for (int i = 0; i < k - 1; i++)
{
ahead = ahead.Next;
}
behind = head;
while (ahead.Next != null)
{
ahead = ahead.Next;
behind = behind.Next;
}
return behind;
}
(2)代码完善
上面的代码存在3处鲁棒性问题:
问题1:输入的head为空指针。由于代码会试图访问空指针指向的内存,程序崩溃。
解决:在处理前增加判断空指针的代码
问题2:输入的以head为头结点的链表的结点总数少于k。由于在for循环中会在链表上向前走k-1步,仍然会由于空指针造成程序崩溃。
解决:在for循环中增加判断下一个节点是否是空指针的代码
问题3:输入的参数k为0。由于k是一个无符号整数,那么在for循环中k-1得到的将不是-1,而是4294967295(无符号的0xFFFFFFFF)。因此for循环执行的次数远远超出我们的预计,同样也会造成程序崩溃。
解决:同(1),在处理前的判断中也判断参数k是否为0。
public static Node FindKthToTail(Node head, uint k)
{
if(head == null || k == 0)
{
return null;
}
Node ahead = head;
Node behind = null;
for (int i = 0; i < k - 1; i++)
{
if(ahead.Next != null)
{
ahead = ahead.Next;
}
else
{
return null;
}
}
behind = head;
while (ahead.Next != null)
{
ahead = ahead.Next;
behind = behind.Next;
}
return behind;
}
画外音:常常有人说大部人都不会考虑得这么完善,但是现实是面试官就喜欢考你有没有考虑这些,即使你平常用不到。虽然我对这种面试也持怀疑态度,但是《剑指Offer》作者的这种态度,即他以一个开发老鸟的角度时时刻刻地站在了鲁棒性、可维护性、可扩展性地角度来告诉即将进入开发一线的菜鸟们做提醒,在开发中需要考虑这些东西,并通过设计测试用例进行单元测试验证结果。这种态度,就是值得我们这些老鸟学习的。
5单元测试
老规矩,仍然需要为我们的代码写单元测试,这也是一个好习惯哦!
其次,功能测试代码:
// 01.测试要找的结点在链表中间
[TestMethod]
public void FindKthNodeTest1()
{
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.Next = node2;
node2.Next = node3;
node3.Next = node4;
node4.Next = node5;
Assert.AreEqual(NodeHelper.FindKthToTail(node1, 4), node2);
}
// 02.测试要找的结点是链表的尾结点
[TestMethod]
public void FindKthNodeTest2()
{
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.Next = node2;
node2.Next = node3;
node3.Next = node4;
node4.Next = node5;
Assert.AreEqual(NodeHelper.FindKthToTail(node1, 1), node5);
}
// 03.测试要找的结点是链表的头结点
[TestMethod]
public void FindKthNodeTest3()
{
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.Next = node2;
node2.Next = node3;
node3.Next = node4;
node4.Next = node5;
Assert.AreEqual(NodeHelper.FindKthToTail(node1, 5), node1);
}
然后,特殊输入测试代码:
// 04.测试空链表
[TestMethod]
public void FindKthNodeTest4()
{
Assert.AreEqual(NodeHelper.FindKthToTail(null, 100), null);
}
// 05.测试输入的第二个参数大于链表的结点总数
[TestMethod]
public void FindKthNodeTest5()
{
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.Next = node2;
node2.Next = node3;
node3.Next = node4;
node4.Next = node5;
Assert.AreEqual(NodeHelper.FindKthToTail(node1, 6), null);
}
// 06.测试输入的第二个参数等于0
[TestMethod]
public void FindKthNodeTest6()
{
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.Next = node2;
node2.Next = node3;
node3.Next = node4;
node4.Next = node5;
Assert.AreEqual(NodeHelper.FindKthToTail(node1, 0), null);
}
最后,测试结果如下:
代码覆盖率如下:
Ref参考资料
何海涛,《剑指Offer》
后台回复:offer,即可获得pdf下载链接哟!
End
欢迎各位读者加入 .NET技术交流群,在公众号后台回复“加群”或者“学习”即可。
文末彩蛋
微信后台回复“asp”,给你:一份全网最强的ASP.NET学习路线图。 回复“cs”,给你:一整套 C# 和 WPF 学习资源! 回复“core”,给你:2019年dotConf大会上发布的.NET core 3.0学习视频! 回复“so”,给你:一套给力的 超级搜索力视频 课程!
转发至朋友圈,是对我最大的支持。
?点击获取文章源码
在看+分享,人间真情