【力扣-JZ22】链表中倒数第k个结点-Toy模板网

这篇具有很好参考价值的文章主要介绍了【力扣-JZ22】链表中倒数第k个结点。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🖊作者 : Djx_hmbb
📘专栏 : 数据结构
😆今日分享 : "把手插进米堆的原因 " : 因为米堆类似于高密度的流体，会给人的手带来较大的压强，这种压强促进静脉血回流，会让人感到生理上的舒服。

✔题目链接:

【力扣-JZ22】

✔题目:

【力扣-JZ22】链表中倒数第k个结点

✔解题思路:

遍历两次(第一反应):

: >先计算链表有多长,然后length–,找到第k个指针

遍历一次->快慢指针(优化):

: >fast指针先走k步,然后slow和fast指针同时向后移动

✔代码详情:

🔎遍历两次:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* cur=pListHead;
    struct ListNode* phead=pListHead;
    //计算链表的长度
    int length=0;
    while(cur){
        cur=cur->next;
        length++;
    }
    if(k>length || k<= 0){
        return NULL;
    }
    //判断是否到倒数第k个结点
    int i = length-k;
    while(i--){
        phead=phead->next;
    }
    //返回倒数第k个的头结点
    return phead;
}

🔎遍历一次->快慢指针:

//优化:快慢指针(遍历一次)
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
    struct ListNode* fast = pListHead;
    struct ListNode* slow = pListHead;
    //使fast与slow相距k个结点
    while (k--) {
        if(fast)
           fast = fast->next;
    }
    //fast与slow同时后移
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    //返回slow指针
    return slow;
}