教你如何輕松學會Java快慢指針法
一、什麼是快慢指針？
快慢指針就是定義兩根指針，移動的速度一快一慢，以此來制造出自己想要的差值。這個差值可以讓我們找到鏈表上相應的節點。
那快慢指針可以解決哪些實際問題呢，接下來我們一起看看吧！
二、使用快慢指針來找到鏈表的中點
1.首先我們設置兩個指針slow和fast，這2個指針的初始位置相同，都指向鏈表的頭結點，然後slow指針每次移動一步，fast指針每次移動兩步；
2.如果鏈表中節點個數為偶數時，當快指針無法繼續移動時，慢指針剛好指向中點；如果鏈表中節點個數為奇數時，當快指針走完，慢指針指向中點的前一個節點。
public ListNode reverseStore(ListNode head) {
// 初始化，讓快指針和慢指針都處於鏈表的頭部
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){//如果快指針並且下一個不為空
fast=fast.next.next;//快指針移動兩個
slow=slow.next;//慢指針移動一個
}
return slow;
}
三、利用快慢指針來判斷鏈表中是否有環
問題描述： 給定一個鏈表，判斷鏈表中是否有環。
以下兩種情況都屬於鏈表中存在環，“0”字型和“6”字型
這個時候我們的解決方案就是利用“快慢指針”， 慢指針針每次走一步，快指針每次走兩步，如果相遇就說明有環，如果有一個為空說明沒有環。代碼比較簡單 （在代碼下面會專門講解思路的，放心！）
public boolean hasCycle(ListNode head) {
if (head == null)
return false;
//快慢兩個指針，初始時都指向鏈表的頭結點
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
//慢指針每次走一步
slow = slow.next;
//快指針每次走兩步
fast = fast.next.next;
//如果相遇，說明有環，直接返回true
if (slow == fast)
return true;
}
//否則就是沒環
return false;
}
到這裡大傢可能就有疑問瞭，為什麼快慢指針就一定能判斷是否有環。我們可以這樣來思考一下，假如有環，那麼快慢指針最終都會走到環上，假如環的長度是m，快慢指針最近的間距是n，如下圖中所示
下面說的兩點相距是指 “快指針還需要多遠可以再次追到慢指針”
快指針每次走兩步，慢指針每次走一步，所以每走一次快慢指針的間距就要縮小一步，在圖一中當走n次的時候就會相遇，在圖二中當走m-n次的時候就會相遇。這樣就解釋清楚瞭讀者的疑問瞭。
四、刪除鏈表的倒數第n個節點
問題描述：刪除倒數第n個節點，那就等於是要我們先找出待刪除元素前一個元素，也就是第n-1個節點。聰明的你肯定發現瞭，我們又把這個問題轉化為找鏈表上的某個節點的問題瞭，這是快慢指針最擅長的場景。
思路很簡單，我們一開始就讓fast指針比slow指針快n+1個元素，接下來，兩個指針都是一步一步來往下走。那麼當fast指針走完時，slow指針就剛剛好停留在第(n-1)個元素上。
//刪除鏈表倒數第n個節點
public ListNode removeBackEndNode(ListNode head, int n) {
if (head == null || head.next == null) {
return null;
}
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
//初始時讓快慢指針都指向鏈表的頭部
ListNode slow = dummyHead;
ListNode fast = dummyHead;
for (int i = 0; i < n + 1; i++) {
fast = fast.next;
}
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next; //為瞭解決斷鏈問題
return dummyHead.next;
}
五、判斷是否是回文鏈表
快指針每次前進兩個單位，慢指針每次前進一個單位並修改其next節點指向前一個節點，所以當快指針到達鏈表末尾的時候（空節點或空節點的前一個節點），慢指針剛好在中間，如下圖所示
此時慢指針繼續向後走，同時開辟一個新節點往前走，看下圖
判斷鏈表中點前後是否相同，達到判斷回文串的目的，如下圖所示
代碼如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null){
return true;
}
ListNode pre = null;//指向前一個節點的指針
ListNode slow = head;//慢指針
ListNode fast = head;//快指針
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
ListNode next = slow.next;
slow.next = pre;//修改慢指針走過的節點指向前一個節點
pre = slow;
slow = next;
}
if(fast != null){
slow = slow.next;
//當長度為奇數是，慢指針需要再走一個單位
}
while(pre!=null) {
//判斷是否為回文串
if(pre.val!=slow.val){
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
}
到此這篇關於教你如何輕松學會Java快慢指針法的文章就介紹到這瞭,更多相關Java快慢指針法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！