中間結點
這種鏈表的題，找第幾個結點，有個很騷的解法，就是用計數器找到那個結點，但是感覺完全避開了他想考察的演算法，這種題應該要能熟練使用快慢指標這種演算法，
這種演算法就根據題目來一邊分析一邊介紹其用處
根據題目
要尋找中間的結點，如果是有兩個中間結點，就回傳第二個結點，
通常是設定一個快指標，一個慢指標，而快指標的速度是慢指標的兩倍，也就是每次快指標一次走兩個元素，而慢指標一次走一個元素，
它要找中間結點，
初始時
移動
再移動
這一步就已經達到目的了，慢指標移動到了中間結點，而此時，回圈應該已經結束了，而快指標則是到了最后一個元素，這應該是一個回圈結束的條件，
當有兩個中間結點時，
移動
移動，慢指標已經到了第一個中間結點，再移動一次就可以到達第二個中間結點，
這種情況下， 快指標應該是走到了最后一個指標的next時，才結束回圈移動，
一種是當快指標移動到最后一個結點時，回圈結束，
一種是當快指標移動到最后一個結點的next時才結束回圈，
總結一下條件是
fast==NULL結束條件對應有兩個中間結點的情況，
fast->next == NULL,是對應只有一個中間結點的情況，
無論哪種情況，都是快指標走兩個結點，慢指標走一個結點，
當回圈遇到兩個條件中的y一個都要結束回圈，回傳慢指標
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
再來看看利用快慢指標的另一道題
倒數第K個結點
這就比較不太一樣，這是規定好特定的結點，但我們結束快指標移動到最后一個結點或NULL時結束，也就是說，當快指標移動到末尾時，慢指標要正好移動到到數第K個結點，
意味著，快指標于慢指標相差K個結點，
可以讓快指標先走K個結點，再快慢指標一起走，當結束時，正好在倒數第K個結點處，
先走K個結點
再兩指標一起走
繼續
繼續
最后一步
因為是倒數第K個快指標如果再最后一個結點，那么慢指標與快指標相差兩個結點，就是倒數第3個結點，所以快指標要在NULL時，才滿足，
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
struct ListNode* fast=head;
struct ListNode* slow=head;
for(int i=0;i<k;i++)
{
if(fast==NULL)
return NULL;
fast=fast->next;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
上面都是常規情況，但是還有一些比較奇怪的測驗用例，
比如k會超過鏈表的結點數，那就只能在快指標達到NULL是就提前結束，
或者本身就是一個空鏈表，那就也是直接結束，
快慢指標感覺挺巧妙的，可以好好理解使用，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/274751.html
標籤：其他
上一篇：HTML5