文章目錄
- 題目要求
- 方法1：統計長度
- 代碼
- 方法2：雙指標
- 代碼
題目要求
鏈接 :鏈表中倒數第k個結點_牛客題霸_牛客網 (nowcoder.com)
本題目和博主曾經寫過的：是一樣的套路！感興趣的老鐵可以翻過去看一下！
舍友僅僅打了一把游戲，我就學會了如何找鏈表的中間結點
方法1：統計長度
思路
- 第一步：遍歷鏈表得出鏈表的長度，記為size，如果k大于鏈表的長度，不可能找到 ，回傳NULL
- 第二步：從頭開始走 size - k 步，就是倒數的第K個結點
從頭開始走：倒數第K個結點的位置是正數的第size-k位置
代碼
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
struct ListNode* cur = pListHead;
//統計鏈表長度
int size = 0;
while(cur)
{
cur = cur->next;
size++;
}
//如果k大于鏈表長度，不可能找到
if(k > size)
{
return NULL;
}
int n = size-k;//倒數第K個結點的位置是正數的第size-k位置
//從頭開始走n步
cur = pListHead;
//cur走n步
while(n--)
{
cur = cur->next;
}
return cur;
}
方法2：雙指標
思路
-
第一步：fast指標先走K步
- ==注意：==如果走k步時：fast走到了NULL，說明k是比鏈表的長度大的，此時不可能找到倒數第K個結點 ->回傳NULL
while(k--) ==>回圈k次 ->走k步
while(--k) ==>回圈k-1次 ->走k-1步
- 第二步：fast和slow一起走，當fast走到NULL時，slow就是倒數第K個結點（奇數個結點個或者偶數個結點都可以）
圖解
代碼
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
//定義雙指標
struct ListNode* fast = pListHead;
struct ListNode* slow = pListHead;
//fast 先走K步
while(k--)
{
//k的大小大于鏈表長度， fast提前走到空
if(fast == NULL)
{
return NULL;
}
fast = fast->next;
}
//fast和slow一起走
//當fast走到NULL 此時slow就是倒數的第K個結點
while(fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/398514.html
標籤：其他
上一篇：unity渲染流水線
下一篇：C語言實作字符界面貪吃蛇