题目
输入一个链表，输出该链表中倒数第k个节点。
为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6.这个链表的倒数第3个节点是值为4的节点。
分析
- 思路1
假设整个链表有n个节点，那么倒数第k个节点就是从头节点开始的第n-k+1个节点。如果我们能够得到链表中节点的个数n，那么只要从头节点开始往后走n-k+1步就可以了。
如何得到节点数n?这个不难，只需要从头开始遍历链表，每经过一个节点，计数器加1就行了。也就是说为我们需要遍历链表两次，第一次统计出链表中节点的个数，第二次就能找到倒数第k个节点。功能可以实现，但是效果不佳
- 思路2
实现只遍历链表一次就能找到倒数第k个节点，我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历，由于两个指针距离保持在k-1，当第一个指针（走在前面的）到达链表的尾节点时，第二个（走在后面）指针正好指向倒数第k个节点
具体分析
下面以有6个节点的链表中找倒数第3个节点。
- 首先用第一个指针从头结点开始向前走（2=3-1）步到达第3个结点，如下图(a)所示。
- 接着把第二个指针初始化指向链表的第一个结点，如下图(b)所示
- 最后让两个指针同时向前遍历，当第一个指针到达链表的尾结点时，第二个指针指向的刚好是倒数第3个结点，如下图(c)所示
download.png
算法实现
struct ListNode
{
int value;
ListNode *next;
};
ListNode* FindKthToTail(ListNode *listHead, unsigned int k)
{
ListNode *head = listHead;
ListNode *behind = nullptr;
// 第一个指针移动k-1个位置
for (unsigned int i = 0; i < k - 1; i++) {
head = head->next;
}
// 将第二个指针设置为头指针
behind = listHead;
// 移动第一个指针一直到尾结点
while (head->next != nullptr) {
head = head->next;
behind = behind->next;
}
return behind;
}
看起来实现没有问题，但是程序很容易奔溃
- 输入的
listHead为空指针。由于代码会试图访问空指针指向的内存，从而造成程序奔溃 - 输入的以
listHead为头结点的链表的结点的总数少于k。由于for循环中会在链表上向前走k-1步，仍然会由于空指针而造成程序的奔溃 - 输入参数k为0，由于k是一个无符号整数，那么在
for循环中k-1得到的将不是-1，而是4294967295（无符号的oxffffffff）。因此，for循环执行的次数远远超出我们的预计，同样会造成程序的奔溃
因此，一定要注意代码的容错处理，保持代码的健壮性。针对上面3个问题，分别处理。
- 如果输入的链表头指针为
nullptr，那么整个链表为空，此时查找倒数第k个结点自然应该返回 -
nullptr。如果输入的k为0，也就是试图查找倒数第0个结点，由于我们计算是从1开始，因此输入0没有实际意义，也可以返回nullptr - 如果链表的结点数少于
k，那么for循环中遍历链表可能会出现指向nullptr的next，因此在for循环中加一个if判断
ListNode* FindKthToTail(ListNode *listHead, unsigned int k)
{
if (listHead == nullptr || k == 0)
return nullptr;
ListNode *head = listHead;
ListNode *behind = nullptr;
// 第一个指针移动k-1个位置
for (unsigned int i = 0; i < k - 1; i++) {
if (head->next != nullptr)
{
head = head->next;
}
else {
return nullptr;
}
}
// 将第二个指针设置为头指针
behind = listHead;
// 移动第一个指针一直到尾结点
while (head->next != nullptr) {
head = head->next;
behind = behind->next;
}
return behind;
}
参考
《剑指offer》
网友评论