当前位置: 代码迷 >> 综合 >> 剑指offer--链表中倒数第k个结点(双指针一次遍历,代码鲁棒性,类似问题)
  详细解决方案

剑指offer--链表中倒数第k个结点(双指针一次遍历,代码鲁棒性,类似问题)

热度:81   发布时间:2024-01-09 07:21:21.0

题目描述:
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

分析:
链表中的倒数第k个结点,我们很容易想到先遍历到链表的尾部,然后向前回溯k个结点,但这需要双向链表才能完成,题目中的链表很显然是单向的。倒数的第k个结点也是正数第n-k+1个结点,我们从头遍历到尾获得链表总结点个数n,然后再一次从头遍历到第n-k+1个结点即可,可这需要两次遍历。我们想一想有没有更好的方法,只需要遍历一次就可以得到我们想要的结果。

我们先让一个指针从头开始走 k-1步,当第一个指针走完k-1步时,它距离尾结点的距离和倒数第k个结点距离头结点的距离相等,(因为倒数第k个结点距离尾结点 k-1步,而现在指针1距离头结点k-1步),此时再让一个新的指针开始从头走,当第一个指针走到尾结点时,第二个指针刚好走到倒数第k个结点的位置。
在这里插入图片描述
根据上面的分析,我们很快能写出代码:

 ListNode* getKthFromEnd(ListNode* head, unsigned int k) {
    ListNode* pAhead = head;ListNode* pBhead = NULL;for(int i = 0 ; i < k - 1; i++){
    if(pAhead->next != NULL)pAhead = pAhead->next;}pBhead = head;while(pAhead->next != NULL){
    pAhead = pAhead->next;pBhead = pBhead->next;}return pBhead;}

但是面试官看到了这样的代码并不会满意,因为我们得代码不够鲁棒,以上面的代码为例,面试官可以找出三种办法让程序崩溃。
(1)输入的head为空指针。由于代码会试图访问空指针指向的内存,从而造成程序崩溃。
(2)输入的以head为头节点的链表的节点总数少于k。由于在for循环中会在链表上向前走k-1步,仍然会由于空指针而造成程序崩溃。
(3)输入的参数k为0。由于k是一个无符号整数,那么在for循环中k-1得到的将不是-1,而是4294967295(无符号的OxFFFFFFFF)。因此,for循环执行的次数远远超出我们的预计,同样也会造成程序崩溃。

对代码进行修改:

  ListNode* getKthFromEnd(ListNode* head, unsigned int k) {
    if(head  == NULL || k == 0)return NULL;ListNode* pAhead = head;ListNode* pBhead = NULL;for(int i = 0 ; i < k - 1; i++){
    if(pAhead->next != NULL)pAhead = pAhead->next;elsereturn NULL;}pBhead = head;while(pAhead->next != NULL){
    pAhead = pAhead->next;pBhead = pBhead->next;}return pBhead;}

类似题目:
求链表的中间节点。如果链表中的节点总数为奇数,则返回中间节点;如果节点总数是偶数,则返回中间两个节点的任意一个。为了解决这个问题,我们也可以定义两个指针,同时从链表的头节点出发,一个指针一次走一步,另一个指针一次走两步。当走得快的指针走到链表的末尾时,走得慢的指针正好在链表的中间。

ps:当我们用一个指针遍历链表不能解决问题的时候,可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些(比如一次在链表上走两步),或者让它先在链表上走若干步。

  相关解决方案