教你如何輕松學(xué)會(huì)Java快慢指針?lè)?/h1>
更新時(shí)間：2021年06月01日 16:25:49 作者：Java全棧研發(fā)大聯(lián)盟
要想把搬磚的效率提高,我們肯定是逃不掉數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)的,這不,可愛的小編今天就和大家一起學(xué)習(xí)來(lái)了,今天給大家分享的是快慢指針,那啥是快慢指針呢,文中有非常詳細(xì)的解釋,需要的朋友可以參考下
一、什么是快慢指針？
快慢指針就是定義兩根指針，移動(dòng)的速度一快一慢，以此來(lái)制造出自己想要的差值。這個(gè)差值可以讓我們找到鏈表上相應(yīng)的節(jié)點(diǎn)。
那快慢指針可以解決哪些實(shí)際問(wèn)題呢，接下來(lái)我們一起看看吧！
二、使用快慢指針來(lái)找到鏈表的中點(diǎn)
1.首先我們?cè)O(shè)置兩個(gè)指針slow和fast，這2個(gè)指針的初始位置相同，都指向鏈表的頭結(jié)點(diǎn)，然后slow指針每次移動(dòng)一步，fast指針每次移動(dòng)兩步；
2.如果鏈表中節(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，當(dāng)快指針無(wú)法繼續(xù)移動(dòng)時(shí)，慢指針剛好指向中點(diǎn)；如果鏈表中節(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，當(dāng)快指針走完，慢指針指向中點(diǎn)的前一個(gè)節(jié)點(diǎn)。
public ListNode reverseStore(ListNode head) {
// 初始化，讓快指針和慢指針都處于鏈表的頭部
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){//如果快指針并且下一個(gè)不為空
fast=fast.next.next;//快指針移動(dòng)兩個(gè)
slow=slow.next;//慢指針移動(dòng)一個(gè)
}
return slow;
}
三、利用快慢指針來(lái)判斷鏈表中是否有環(huán)
問(wèn)題描述： 給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。
以下兩種情況都屬于鏈表中存在環(huán)，“0”字型和“6”字型
這個(gè)時(shí)候我們的解決方案就是利用“快慢指針”， 慢指針針每次走一步，快指針每次走兩步，如果相遇就說(shuō)明有環(huán)，如果有一個(gè)為空說(shuō)明沒(méi)有環(huán)。代碼比較簡(jiǎn)單 （在代碼下面會(huì)專門講解思路的，放心?。?/p>
public boolean hasCycle(ListNode head) {
if (head == null)
return false;
//快慢兩個(gè)指針，初始時(shí)都指向鏈表的頭結(jié)點(diǎn)
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
//慢指針每次走一步
slow = slow.next;
//快指針每次走兩步
fast = fast.next.next;
//如果相遇，說(shuō)明有環(huán)，直接返回true
if (slow == fast)
return true;
}
//否則就是沒(méi)環(huán)
return false;
}
到這里大家可能就有疑問(wèn)了，為什么快慢指針就一定能判斷是否有環(huán)。我們可以這樣來(lái)思考一下，假如有環(huán)，那么快慢指針最終都會(huì)走到環(huán)上，假如環(huán)的長(zhǎng)度是m，快慢指針最近的間距是n，如下圖中所示
下面說(shuō)的兩點(diǎn)相距是指 “快指針還需要多遠(yuǎn)可以再次追到慢指針”
快指針每次走兩步，慢指針每次走一步，所以每走一次快慢指針的間距就要縮小一步，在圖一中當(dāng)走n次的時(shí)候就會(huì)相遇，在圖二中當(dāng)走m-n次的時(shí)候就會(huì)相遇。這樣就解釋清楚了讀者的疑問(wèn)了。
四、刪除鏈表的倒數(shù)第n個(gè)節(jié)點(diǎn)
問(wèn)題描述：刪除倒數(shù)第n個(gè)節(jié)點(diǎn)，那就等于是要我們先找出待刪除元素前一個(gè)元素，也就是第n-1個(gè)節(jié)點(diǎn)。聰明的你肯定發(fā)現(xiàn)了，我們又把這個(gè)問(wèn)題轉(zhuǎn)化為找鏈表上的某個(gè)節(jié)點(diǎn)的問(wèn)題了，這是快慢指針最擅長(zhǎng)的場(chǎng)景。
思路很簡(jiǎn)單，我們一開始就讓fast指針比slow指針快n+1個(gè)元素，接下來(lái)，兩個(gè)指針都是一步一步來(lái)往下走。那么當(dāng)fast指針走完時(shí)，slow指針就剛剛好停留在第(n-1)個(gè)元素上。
//刪除鏈表倒數(shù)第n個(gè)節(jié)點(diǎn)
public ListNode removeBackEndNode(ListNode head, int n) {
if (head == null || head.next == null) {
return null;
}
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
//初始時(shí)讓快慢指針都指向鏈表的頭部
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; //為了解決斷鏈問(wèn)題
return dummyHead.next;
}
五、判斷是否是回文鏈表
快指針每次前進(jìn)兩個(gè)單位，慢指針每次前進(jìn)一個(gè)單位并修改其next節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)，所以當(dāng)快指針到達(dá)鏈表末尾的時(shí)候（空節(jié)點(diǎn)或空節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)），慢指針剛好在中間，如下圖所示
此時(shí)慢指針繼續(xù)向后走，同時(shí)開辟一個(gè)新節(jié)點(diǎn)往前走，看下圖
判斷鏈表中點(diǎn)前后是否相同，達(dá)到判斷回文串的目的，如下圖所示
代碼如下：
/**
* 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;//指向前一個(gè)節(jié)點(diǎn)的指針
ListNode slow = head;//慢指針
ListNode fast = head;//快指針
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
ListNode next = slow.next;
slow.next = pre;//修改慢指針走過(guò)的節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)
pre = slow;
slow = next;
}
if(fast != null){
slow = slow.next;
//當(dāng)長(zhǎng)度為奇數(shù)是，慢指針需要再走一個(gè)單位
}
while(pre!=null) {
//判斷是否為回文串
if(pre.val!=slow.val){
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
}
到此這篇關(guān)于教你如何輕松學(xué)會(huì)Java快慢指針?lè)ǖ奈恼戮徒榻B到這了,更多相關(guān)Java快慢指針?lè)▋?nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
-
java基礎(chǔ)之Integer與int類型輸出示例解析
這篇文章主要為大家介紹了java基礎(chǔ)之Integer與int類型輸出示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪 2023-06-06
-
這篇文章主要為大家詳細(xì)介紹了Springboot網(wǎng)站第三方登錄 ，微信登錄，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下 2017-12-12
-
SpringCloud版本問(wèn)題報(bào)錯(cuò)及解決方法
這篇文章主要介紹了SpringCloud版本問(wèn)題報(bào)錯(cuò)及解決方法,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下 2019-07-07
-
Spring data jpa的使用與詳解(復(fù)雜動(dòng)態(tài)查詢及分頁(yè)，排序)
這篇文章主要介紹了Spring data jpa的使用與詳解(復(fù)雜動(dòng)態(tài)查詢及分頁(yè)，排序)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧 2020-11-11
-
本文詳細(xì)講解了Java基礎(chǔ)篇之反射機(jī)制，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下 2022-01-01
-
這篇文章主要為大家詳細(xì)介紹了如何基于Java編寫一個(gè)神奇的代碼恢復(fù)工具,文中的示例代碼簡(jiǎn)潔易懂,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下 2024-04-04
-
這篇文章主要介紹了Java單例模式和多例模式,結(jié)合實(shí)例形式分析了java單例模式與多例模式的定義及使用技巧,需要的朋友可以參考下 2019-07-07
-
聊聊Kotlin?中?lateinit?和?lazy?的原理區(qū)別
使用 Kotlin 進(jìn)行開發(fā)，對(duì)于 latelinit 和 lazy 肯定不陌生。但其原理上的區(qū)別，可能鮮少了解過(guò)，借著本篇文章普及下這方面的知識(shí)，感興趣的朋友一起看看吧 2022-07-07
-
Spring Boot中的@ConfigurationProperties注解解讀
在SpringBoot框架中,@ConfigurationProperties注解是處理外部配置的強(qiáng)大工具,它允許開發(fā)者將配置文件中的屬性自動(dòng)映射到Java類的字段上,實(shí)現(xiàn)配置的集中管理和類型安全,通過(guò)定義配置類并指定前綴,可以將配置文件中的屬性綁定到Java對(duì)象 2024-10-10
-
Idea中maven無(wú)法下載依賴包問(wèn)題解決
用過(guò)idea開發(fā)過(guò)項(xiàng)目的同學(xué)，偶爾會(huì)遇到項(xiàng)目中有一些依賴沒(méi)法下載，或者依賴包已經(jīng)有項(xiàng)目卻無(wú)法掃到的問(wèn)題，本文就詳細(xì)的介紹了解決方法，感興趣的可以了解一下 2020-08-08
最新評(píng)論
一、什么是快慢指針？
快慢指針就是定義兩根指針，移動(dòng)的速度一快一慢，以此來(lái)制造出自己想要的差值。這個(gè)差值可以讓我們找到鏈表上相應(yīng)的節(jié)點(diǎn)。
那快慢指針可以解決哪些實(shí)際問(wèn)題呢，接下來(lái)我們一起看看吧！
二、使用快慢指針來(lái)找到鏈表的中點(diǎn)
1.首先我們?cè)O(shè)置兩個(gè)指針slow和fast，這2個(gè)指針的初始位置相同，都指向鏈表的頭結(jié)點(diǎn)，然后slow指針每次移動(dòng)一步，fast指針每次移動(dòng)兩步；
2.如果鏈表中節(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，當(dāng)快指針無(wú)法繼續(xù)移動(dòng)時(shí)，慢指針剛好指向中點(diǎn)；如果鏈表中節(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，當(dāng)快指針走完，慢指針指向中點(diǎn)的前一個(gè)節(jié)點(diǎn)。
public ListNode reverseStore(ListNode head) {
// 初始化，讓快指針和慢指針都處于鏈表的頭部
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){//如果快指針并且下一個(gè)不為空
fast=fast.next.next;//快指針移動(dòng)兩個(gè)
slow=slow.next;//慢指針移動(dòng)一個(gè)
}
return slow;
}
三、利用快慢指針來(lái)判斷鏈表中是否有環(huán)
問(wèn)題描述： 給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。
以下兩種情況都屬于鏈表中存在環(huán)，“0”字型和“6”字型
這個(gè)時(shí)候我們的解決方案就是利用“快慢指針”， 慢指針針每次走一步，快指針每次走兩步，如果相遇就說(shuō)明有環(huán)，如果有一個(gè)為空說(shuō)明沒(méi)有環(huán)。代碼比較簡(jiǎn)單 （在代碼下面會(huì)專門講解思路的，放心?。?/p>
public boolean hasCycle(ListNode head) {
if (head == null)
return false;
//快慢兩個(gè)指針，初始時(shí)都指向鏈表的頭結(jié)點(diǎn)
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
//慢指針每次走一步
slow = slow.next;
//快指針每次走兩步
fast = fast.next.next;
//如果相遇，說(shuō)明有環(huán)，直接返回true
if (slow == fast)
return true;
}
//否則就是沒(méi)環(huán)
return false;
}
到這里大家可能就有疑問(wèn)了，為什么快慢指針就一定能判斷是否有環(huán)。我們可以這樣來(lái)思考一下，假如有環(huán)，那么快慢指針最終都會(huì)走到環(huán)上，假如環(huán)的長(zhǎng)度是m，快慢指針最近的間距是n，如下圖中所示
下面說(shuō)的兩點(diǎn)相距是指 “快指針還需要多遠(yuǎn)可以再次追到慢指針”
快指針每次走兩步，慢指針每次走一步，所以每走一次快慢指針的間距就要縮小一步，在圖一中當(dāng)走n次的時(shí)候就會(huì)相遇，在圖二中當(dāng)走m-n次的時(shí)候就會(huì)相遇。這樣就解釋清楚了讀者的疑問(wèn)了。
四、刪除鏈表的倒數(shù)第n個(gè)節(jié)點(diǎn)
問(wèn)題描述：刪除倒數(shù)第n個(gè)節(jié)點(diǎn)，那就等于是要我們先找出待刪除元素前一個(gè)元素，也就是第n-1個(gè)節(jié)點(diǎn)。聰明的你肯定發(fā)現(xiàn)了，我們又把這個(gè)問(wèn)題轉(zhuǎn)化為找鏈表上的某個(gè)節(jié)點(diǎn)的問(wèn)題了，這是快慢指針最擅長(zhǎng)的場(chǎng)景。
思路很簡(jiǎn)單，我們一開始就讓fast指針比slow指針快n+1個(gè)元素，接下來(lái)，兩個(gè)指針都是一步一步來(lái)往下走。那么當(dāng)fast指針走完時(shí)，slow指針就剛剛好停留在第(n-1)個(gè)元素上。
//刪除鏈表倒數(shù)第n個(gè)節(jié)點(diǎn)
public ListNode removeBackEndNode(ListNode head, int n) {
if (head == null || head.next == null) {
return null;
}
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
//初始時(shí)讓快慢指針都指向鏈表的頭部
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; //為了解決斷鏈問(wèn)題
return dummyHead.next;
}
五、判斷是否是回文鏈表
快指針每次前進(jìn)兩個(gè)單位，慢指針每次前進(jìn)一個(gè)單位并修改其next節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)，所以當(dāng)快指針到達(dá)鏈表末尾的時(shí)候（空節(jié)點(diǎn)或空節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)），慢指針剛好在中間，如下圖所示
此時(shí)慢指針繼續(xù)向后走，同時(shí)開辟一個(gè)新節(jié)點(diǎn)往前走，看下圖
判斷鏈表中點(diǎn)前后是否相同，達(dá)到判斷回文串的目的，如下圖所示
代碼如下：
/**
* 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;//指向前一個(gè)節(jié)點(diǎn)的指針
ListNode slow = head;//慢指針
ListNode fast = head;//快指針
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
ListNode next = slow.next;
slow.next = pre;//修改慢指針走過(guò)的節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)
pre = slow;
slow = next;
}
if(fast != null){
slow = slow.next;
//當(dāng)長(zhǎng)度為奇數(shù)是，慢指針需要再走一個(gè)單位
}
while(pre!=null) {
//判斷是否為回文串
if(pre.val!=slow.val){
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
}
到此這篇關(guān)于教你如何輕松學(xué)會(huì)Java快慢指針?lè)ǖ奈恼戮徒榻B到這了,更多相關(guān)Java快慢指針?lè)▋?nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
-
java基礎(chǔ)之Integer與int類型輸出示例解析
這篇文章主要為大家介紹了java基礎(chǔ)之Integer與int類型輸出示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-06-06 - 這篇文章主要為大家詳細(xì)介紹了Springboot網(wǎng)站第三方登錄 ，微信登錄，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-12-12
-
SpringCloud版本問(wèn)題報(bào)錯(cuò)及解決方法
這篇文章主要介紹了SpringCloud版本問(wèn)題報(bào)錯(cuò)及解決方法,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07 -
Spring data jpa的使用與詳解(復(fù)雜動(dòng)態(tài)查詢及分頁(yè)，排序)
這篇文章主要介紹了Spring data jpa的使用與詳解(復(fù)雜動(dòng)態(tài)查詢及分頁(yè)，排序)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11 - 本文詳細(xì)講解了Java基礎(chǔ)篇之反射機(jī)制，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-01-01
- 這篇文章主要為大家詳細(xì)介紹了如何基于Java編寫一個(gè)神奇的代碼恢復(fù)工具,文中的示例代碼簡(jiǎn)潔易懂,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-04-04
- 這篇文章主要介紹了Java單例模式和多例模式,結(jié)合實(shí)例形式分析了java單例模式與多例模式的定義及使用技巧,需要的朋友可以參考下2019-07-07
-
聊聊Kotlin?中?lateinit?和?lazy?的原理區(qū)別
使用 Kotlin 進(jìn)行開發(fā)，對(duì)于 latelinit 和 lazy 肯定不陌生。但其原理上的區(qū)別，可能鮮少了解過(guò)，借著本篇文章普及下這方面的知識(shí)，感興趣的朋友一起看看吧2022-07-07 -
Spring Boot中的@ConfigurationProperties注解解讀
在SpringBoot框架中,@ConfigurationProperties注解是處理外部配置的強(qiáng)大工具,它允許開發(fā)者將配置文件中的屬性自動(dòng)映射到Java類的字段上,實(shí)現(xiàn)配置的集中管理和類型安全,通過(guò)定義配置類并指定前綴,可以將配置文件中的屬性綁定到Java對(duì)象2024-10-10 -
Idea中maven無(wú)法下載依賴包問(wèn)題解決
用過(guò)idea開發(fā)過(guò)項(xiàng)目的同學(xué)，偶爾會(huì)遇到項(xiàng)目中有一些依賴沒(méi)法下載，或者依賴包已經(jīng)有項(xiàng)目卻無(wú)法掃到的問(wèn)題，本文就詳細(xì)的介紹了解決方法，感興趣的可以了解一下2020-08-08