文章目錄
- Leetcode876.鏈表的中間結點
- 鏈表中倒數第k個結點
Leetcode876.鏈表的中間結點
相信對于學習鏈表的初學者來說，首次看到這個題目時，首先想到的應該是通過對整個鏈表進行一遍遍歷求出鏈表節點的個數，然后再通過回圈來找到中間節點(實不相瞞我第一次也是這樣想的)，但是通過兩次回圈，不免增加了代碼量和時間復雜度，那么，接下來就介紹一下最優的解題思路，
最優思路
定義兩個指標，其中一個指標為慢指標，另一個指標為快指標，對本題而言，慢指標每次走一步(向前移動一個節點)，快指標每次走兩步(向前移動兩個節點)，當快指標走到鏈表末尾時，此時的慢指標就正好移動到鏈表的中間節點，圖解如下：
代碼如下：
struct ListNode* middleNode(struct ListNode* head){
struct ListNode*n1=head,*n2=head; //定義兩個指標，分別為快慢指標
while(n2 && n2->next) //當快指標指向最后一個節點或者指向NULL時結束
{
n1=n1->next; //每次向前走一步
n2=n2->next->next; //每次向前走兩步
}
return n1;
}
鏈表中倒數第k個結點
根據上一題的思路，我們可以借鑒雙指標來解決這道題，即先讓一個指標先向前走動 K 步，再讓另一個指標從頭節點開始走，當前一個指標走到鏈表尾節點的 next 域時（即指向NULL時），此時的后一個指標就指向的鏈表中的倒數第K個節點，圖解如下：
代碼如下：
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
ListNode* slow=pListHead;
ListNode*fast=pListHead;
while(k--) //使fast指標向向前走動K個節點
{
if(fast==NULL)
return NULL; //處理特殊情況，當鏈表為空鏈表時，回傳NULL(下同)
fast=fast->next;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
if(slow==NULL)
{
return NULL; //處理特殊情況，同上
}
return slow;
}
};
通過以上兩題我們可以知道，在通常需要求鏈表中某個位置的節點時，除了使用遍歷的方法外，還應當想到比較優的雙指標(快慢指標)的方法，這樣的時間復雜度和代碼量都得到了很好的優化，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/356984.html
標籤：其他
上一篇：【資料結構】二叉樹(順序結構+鏈式結構+堆排序+Topk問題)
下一篇：資料結構——堆疊的實作