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

news/2024/12/29 12:15:58/

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

文章目录

✔题目链接:
✔题目:
✔解题思路:
- 遍历两次(第一反应):
- 遍历一次->快慢指针(优化):
✔代码详情:
- 🔎遍历两次:
- 🔎遍历一次->快慢指针:
- 🔎图解:
- 家人们,点个![请添加图片描述](https://img-blog.csdnimg.cn/11dae7d2dd1b46b2b021edaccee67cf1.jpeg)再走呗~

✔题目链接:

【力扣-JZ22】

✔题目:

在这里插入图片描述

✔解题思路:

遍历两次(第一反应):

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

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

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

✔代码详情:

🔎遍历两次:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code herestruct 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;
}