网站服务器在哪租,网站源码大全最新,外贸业务怎么利用网站开发客户,电商网站建设源代码面试题15#xff1a;链表中倒数第k个结点 题目#xff1a;输入一个链表#xff0c;输出该链表中倒数第 k 个结点。为了符合大多数人的习惯#xff0c;本题从1 开始计数#xff0c;即链表的尾结点是倒数第1 个结点。例如一个链表有6个结点#xff0c;从头结点开始它们的值…面试题15链表中倒数第k个结点 题目输入一个链表输出该链表中倒数第 k 个结点。为了符合大多数人的习惯本题从1 开始计数即链表的尾结点是倒数第1 个结点。例如一个链表有6个结点从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。 链表结点定义如下
struct ListNode
{int value;ListNode *next;
};为了实现只遍历链表一次就能找到倒数第 k 个结点我们可以定义两个指针。 第一个指针从链表的头指针开始遍历向前走k-1第二个指针保持不动 从第 k 步开始第二个指针也开始从链表的头指针开始遍历。 由于两个指针的距离保持在k-1当第一个走在前面的指针到达链表的尾结点时第二个指针走在后面的指针正好是倒数第k个结点。
代码如下:
ListNode *FindKthToTail(ListNode *pListHead, unsigned int k)
{ListNode *pAhead pListHead;ListNode *pBehind nullptr;for (unsigned int i 0; i k - 1; i){pAhead pAhead-next;}pBehind pListHead;while (pAhead-next ! nullptr){pAhead pAhead-next;pBehind pBehind-next;}return pBehind;
}以上面的代码为例面试官可以找出3种办法让这段代码崩溃
输入的pListHead为空指针。由于代码会试图访问空指针指向的内存程序崩溃。输入的以pListHead为头结点的链表的结点总数少于k。由于在for循环中会在链表上向前走k-1步仍然会由于空指针造成程序崩溃。输入的参数k为0。由于k是一个无符号整数那么在for循环中k-1得到的将不是-1而是4294967295无符号的0xFFFFFFFF。因此for循环执行的次数远远超出我们的预计同样也会造成程序崩溃。
写代码要特别注意鲁棒性。
针对前面指出的 3 个问题我们要分别处理。
如果输入的链表头指针为 NULL那么整个链表为空此时查找倒数第 k 个结点自然应该返回NULL。如果输入的k是0也就是试图查找倒数第0个结点由于我们计数是从1 开始的因此输入0 没有实际意义也可以返回NULL。如果链表的结点数少于 k在 for 循环中遍历链表可能会出现指向 NULL的m_pNext因此我们在for循环中应该加一个if判断。
修改之后的代码如下
ListNode *FindKthToTail(ListNode *pListHead, unsigned int k)
{if (pListHead nullptr || k 0) return nullptr;ListNode *pAhead pListHead;ListNode *pBehind nullptr;for (unsigned int i 0; i k - 1; i){if (pAhead-next ! nullptr){pAhead pAhead-next;}else return nullptr;}pBehind pListHead;while (pAhead-next ! nullptr){pAhead pAhead-next;pBehind pBehind-next;}return pBehind;
}测试用例 ● 功能测试第k 个结点在链表的中间第k 个结点是链表的头结点第k个结点是链表的尾结点。 ● 特殊输入测试链表头结点为 NULL 指针链表的结点总数少于kk等于0。 本题考点 ● 考查对链表的理解。 ● 考查代码的鲁棒性。鲁棒性是解决这道题的关键所在。如果应聘者写出的代码有着多处崩溃的潜在风险那么他是很难通过这轮面试的。 相关题目 ● 求链表的中间结点。如果链表中结点总数为奇数返回中间结点如果结点总数是偶数返回中间两个结点的任意一个。为了解决这个问题我们也可以定义两个指针同时从链表的头结点出发一个指针一次走一步另一个指针一次走两步。当走得快的指针走到链表的末尾时走得慢的指针正好在链表的中间。 ● 判断一个单向链表是否形成了环形结构。和前面的问题一样定义两个指针同时从链表的头结点出发一个指针一次走一步另一个指针一次走两步。如果走得快的指针追上了走得慢的指针那么链表就是环形链表如果走得快的指针走到了链表的末尾m_pNext指向NULL都没有追上第一个指针那么链表就不是环形链表。
