每日一题---OJ题: 返回倒数第 k 个节点

片头

嗨! 小伙伴们,大家好! 今天我们来一起学习这道OJ题---返回倒数第k个结点,准备好了吗? 我们开始咯!

比如: 总共有5个结点,分别为 1->2->3->4->5 , 找倒数第一个结点,也就是"5"

题目很容易理解,我们先提供第一种思路

思路一: 假设链表长度为 n , 题目要求返回倒数第 k 个结点,那么我们就从前往后数,从第一个结点开始,跳 n-k 次,最终找到这个结点,并且返回

代码如下:

typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){
        //求链表长度
        int len = 0;
        ListNode* pcur = head;
        while(pcur!=NULL){
            pcur = pcur->next;
            len++;
        }

        //倒数第k个结点
        //从第一个结点开始,跳4次,跳 n-k 次
        pcur = head;
        int count = len-k;
        while(count--){
            pcur = pcur->next;
        }
        return pcur->val;//返回该节点的值
}

那有没有另外一种思路呢? 当然有,我们一起来看看吧~

思路二: 定义2个指针,也就是快慢指针,快指针先走 k 步, 再两个指针一起走,直到快指针指向空。

初始时,fast 和 slow 指针都指向头结点

fast 指针先走 k 步,假如这里 k = 3,我们求倒数第3个结点,fast指针走到"4"的位置

接着让 slow 和 fast 指针一起往后走,直到 fast 指向空

第一次：

第二次：

此时 fast 指针指向空, slow指针指向的结点刚好是倒数第3个结点,返回slow指向结点的数据域

代码如下:

typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){
        ListNode* fast = head;//初始时,fast指针指向头结点
        ListNode* slow = head;//初始时,slow指针指向头结点

        while(k--){           //fast指针先走 k 步
            fast = fast->next;
        }

        while(fast != NULL){  //当fast指针不为空时,进入循环
            fast = fast->next;//fast指针走一步
            slow = slow->next;//slow指针走一步
        }
//此时slow指针指向的结点就是倒数第k个结点,返回slow指针指向结点的数据值
        return slow->val;     
}

嗯,还有一种思路但是和思路2类似,我们一起来看看

思路3: 定义2个指针,也就是快慢指针,快指针先走 k-1 步, 再两个指针一起走,直到快指针的next指针指向空。

初始时, fast 指针和 slow 指针都指向头结点。

fast 指针先走 k-1 步,假如这里 k = 3,我们求倒数第3个结点,fast指针走到"3"的位置

我们再让slow指针和fast指针一起走, 直到fast的next指针为空

第一次:

第二次:

此时,fast 的next指针指向空, 那么退出循环

代码如下:

typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){
        ListNode* fast = head;//定义一个fast指针,初始时指向头结点
        ListNode* slow = head;//定义一个slow指针,初始时指向头结点

        while(--k){           //fast指针先走 k-1 步
            fast = fast->next;
        }  

        while(fast->next != NULL){  //当fast的next指针不为空时,进入循环
            fast = fast->next;      //fast指针走一步
            slow = slow->next;      //slow指针走一步
        }  

        return slow->val;           //最后返回slow指针指向结点的数据域
}