雙指針算法之快慢指針(二)：力扣【尋找鏈表的第N個點】leetcode-876、19

看完本文，可以去解決力扣的 867 題和 19 題
以往參考：雙指針算法之快慢指針(一)：力扣【判斷鏈表是否有環】leetcode-141、142

直奔主題，上面的那一篇文章，是對于有環的鏈表的處理，判斷是不是有環，尋找環的開始結點，其實在實際場景中，同樣需要查詢，查詢鏈表的中間結點，或者查詢鏈表的倒數多少位置的結點等等。

1、尋找鏈表的中點-leetcode-876（簡單）

如果鏈表的長度是奇數，那么返回鏈表的中間結點。
如果鏈表的長度是偶數，那么返回鏈表的中間結點靠右邊的結點。

有了上一次文章的鋪墊，下面直接上代碼

class Solution { public:ListNode* middleNode(ListNode* head) {ListNode *fast,*slow;fast = slow = head;while (fast != NULL && fast->next != NULL) {fast = fast->next->next; // 一次兩步slow = slow->next; // 一次一步}// slow 就在中間位置return slow;} };

有人可能會有疑問，為什么偶數長度的時候沒有看見處理？
其實稍微畫幾個步驟就能夠明白了

我們看一下步驟 2
1、如果此時鏈表長度是 3 ，奇數的時候；
fast->next = NULL，不滿足while循環的條件 while (fast != NULL && fast->next != NULL)；
所以返回的 slow 就是 2，就是當前鏈表的中點
2、同樣還是步驟2，如果此時鏈表長度是 4 ，偶數的時候；
fast->next != NULL，滿足while循環的條件 while (fast != NULL && fast->next != NULL)；
于是就到了步驟3，此時fast 快指針指向的是 5 ，是 NULL，慢指針 slow指向的是 3，就是中點偏右的點

2、刪除鏈表的倒數第N個結點（中等）

這道題相對而言就更簡單了。
使用快慢指針，速度都是一步，快指針先走 n 步，隨后快慢指針再一起開始前進
等到快指針指向 NULL 的時候，慢指針的位置就是倒數第N個結點了，隨后刪除即可

class Solution { public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode *fast,*slow;fast = slow = head;//fast先走n步，如果到頭，倒數的n就是第一個while (n-- >0) {fast = fast->next;}if (fast == NULL) {return head->next;}while (fast != NULL && fast->next != NULL) {fast = fast->next;slow = slow->next;}//刪除slow->next = slow->next->next;return head;} };

總結

以上是生活随笔為你收集整理的双指针算法之快慢指针(二)：力扣【寻找链表的第N个点】leetcode-876、19的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。