雙指針?biāo)惴ㄖ炻羔?/h2>

在上一篇博文中，我們討論了左右對撞指針，今天我們來討論另外一種雙指針?biāo)惴ā炻羔槨?/p>

I. 定義

快慢指針是雙指針?biāo)惴ㄖ械囊环N。不同于左右對撞指針，快慢指針中的兩個指針是從同一側(cè)但以不同的策略移動的指針。因此，兩個指針中會有一個移動較快的快指針（fast）和一個較慢的慢指針（slow）。當(dāng)快指針移動到數(shù)組的頂端時，停止遍歷或進(jìn)行新一輪遍歷。

Note：由于鏈表中指針無法往回走的特性，快慢指針在鏈表中使用非常頻繁。遇到鏈表題目時，應(yīng)當(dāng)考慮快慢指針。

II. 實現(xiàn)方法

實現(xiàn)快慢指針?biāo)惴ㄍǔ７譃橐韵聨讉€步驟：

1. 將快慢兩個指針指向集合的頭部。
2. 移動快指針到滿足快慢指針的位置。
3. 通過while循環(huán)使用快慢指針遍歷集合。
4. 返回結(jié)果

Note：為了避免fast指向null，有時需要將快慢指針指向集合的head的前一位。實現(xiàn)這個步驟，我們需要定義一個不干擾結(jié)果的對象dummy，并將它的next對象指向集合的head。

III. 經(jīng)典習(xí)題

1) Remove Nth Node From End of List(Leetcode 19)

Given a linked list, remove the n-th node from the end of list and return its head.

圖片名稱

這道題目是一道典型的在鏈表上使用快慢指針解決的題目。題意為輸入一個鏈表和一個Integer n，刪除其從后往前數(shù)第n位的值，并返回新的鏈表。n的輸入永遠(yuǎn)是合規(guī)的。

這道題目的解題 思路是這樣的。我們設(shè)置快慢兩個指針，令快指針先走n步，再同時移動快慢指針，直到快指針走到鏈表的底部。這時候刪除慢指針指向的后一個對象，然后返回新的鏈表。

Note：為了避免輸入長度為1的鏈表，刪除其中唯一的一項時，快指針會首先走一位指向null的情況出現(xiàn)，我們要在鏈表的head前增設(shè)一個dummy對象。

解題步驟如下：

1. 設(shè)置dummy對象其next指向head，避免fast指到null。

ListNode dummy = new ListNode(0);
dummy.next = head;

1. 設(shè)置快慢兩個指針指向dummy。

ListNode slow = dummy;
ListNode fast = dummy;

1. 通過for循環(huán)讓快指針先移動n次。

for (int i=0; i<n; i++){
  fast = fast.next;
}

1. 通過while循環(huán)同時移動快慢兩個指針，直到快指針指到鏈表的底部為止。

while(fast.next != null){
  slow = slow.next;
  fast = fast.next;
}

1. 斷開slow和它下一位的連接，并使其連接它的下下位，這樣就完成了刪除工作。

slow.next = slow.next.next;

1. 返回新的鏈表。

return dummy.next;

代碼

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0); 
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        for (int i = 0; i<n;i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

2) Swap Nodes in Pairs(Leetcode 24)

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

圖片名稱

這道題的意思是輸入一個鏈表，將其對象的位置兩兩互換（第一位和第二位互換，第三位和第四位互換…）

這道題的解題思路是這樣的。首先令快指針比慢指針走的快一步，定義一個int i來計算對象的位置，是奇數(shù)位還是偶數(shù)位。如果是偶數(shù)位就把快慢兩個指針的值互換，如果是奇數(shù)位就不變。接著開啟while循環(huán)直到快指針指到null位置。最后返回鏈表。

解題步驟如下：

1. 如果輸入的鏈表為null，返回null。

if (head == null) return head;

1. 定義快慢兩個指針，慢指針指向頭部，快指針指到第二位。

ListNode slow = head;
ListNode fast = head.next;

1. 定義int i, 開啟while循環(huán)，當(dāng)快指針指到null時停止循環(huán)。如果i為偶數(shù)，交換快慢兩個指針指向的對象的值，如果i為奇數(shù)則不變。

int i=0;
while(fast != null){
  if (i%2 == 0){
    int val = slow.val;
    slow.val = fast.val;
    fast.val = val;
  }
  slow = slow.next;
  fast = fast.next;
  i++;
}

1. 返回新的鏈表。

return head;

代碼

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        int i = 0;
        while (fast != null){
            if (i%2 == 0){
                int val = slow.val;
                slow.val = fast.val;
                fast.val = val;
            }
            slow = slow.next;
            fast = fast.next;
            i++;
        }
        return head;
    }
}

IV. 總結(jié)

快慢指針?biāo)惴ㄊ且环N通常在鏈表中使用的功能強大的雙指針?biāo)惴āＦ洳襟E為設(shè)置快慢兩個指針從同一個方向以不同的移動條件遍歷集合從而達(dá)到相應(yīng)的目的。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。