前言
通常用在線性的資料結構中，例如鍊錶和陣列。
指標其實就是資料的索引或是鍊錶的結點。兩個指針朝著左右兩個方向移動，直到滿足搜尋條件。雙指針可分為同向雙指針、異向雙指針、快慢指針、滑動視窗。根據需求選擇雙指標的模型，例如刪除陣列或鍊錶中重複的元素，同向雙指標（線性表前提是有序的）； 快慢指標一般用在鍊錶中，例如求鍊錶的中點、判斷鍊錶是否有環、判斷鍊錶換的起點、環的長度、以及鍊錶的倒數第K個元素； 例如在二分查找中用的就是異向雙指針； 滑動窗口其實就是在數組或者鍊錶某個區間上的操作，例如求最長/最短子字串或是特定子字串的長度要求。
1.判斷鍊錶是否有環
力扣141題
#給你一個鍊錶的頭節點 head ，判斷鍊錶中是否有環。
如果鍊錶中有某個節點，可以透過連續追蹤 next 指標再次到達，則鍊錶中存在環。為了表示給定鍊錶中的環，評測系統內部使用整數 pos 來表示鍊錶尾連接到鍊錶中的位置（索引從 0 開始）。注意：pos 不作為參數進行傳遞 。只是為了標識鍊錶的實際情況。
如果鍊錶中存在環 ，則傳回 true 。否則，傳回 false 。
程式碼實作
public class Solution {
//快慢指针法
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode low = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
low = low.next;
//此时相遇了
if(fast == low){
return true;
}
}
return false;
}
}2.找出鍊錶中間的元素
力扣876題
給定一個頭結點為head 的非空單鍊錶，傳回鍊錶的中間結點。
如果有兩個中間結點，則傳回第二個中間結點。
程式實作
//快慢指针法
public ListNode middleNode(ListNode head) {
ListNode low = head,fast = head;
while(fast != null && fast.next != null){
//慢指针走一步
low = low.next;
//快指针走两步
fast = fast.next.next;
}
//奇数，fast.next = null时，low即为所求
//偶数，fsat == null时，low即为所求
return low;
}3.奇偶排序前奇後偶
力扣328題
給定單鍊錶的頭節點head ，將所有索引為奇數的節點和索引為偶數的節點分別組合在一起，然後傳回重新排序的清單。
第一個節點的索引被認為是 奇數 ， 第二個節點的索引為 偶數 ，以此類推。
程式碼實作
public ListNode oddEvenList(ListNode head) {
if(head == null){
return head;
}
ListNode fastHead = head.next;
ListNode lowTail = head;//奇数链表
ListNode fastTail = fastHead;//偶数链表
while(fastTail != null && fastTail.next != null){
//更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点
lowTail.next = fastTail.next;
lowTail = lowTail.next;
// 更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点
fastTail.next = lowTail.next;
fastTail = fastTail.next;
}
//合并两个链表
lowTail.next = fastHead;
return head;
}4.刪除排序鍊錶的重複元素
力扣82題
給定一個已排序的鍊錶的頭head ， 刪除原始鍊錶中所有重複數字的節點，只留下不同的數字。傳回已排序的鍊錶
程式碼實作
public ListNode deleteDuplicates(ListNode head) {
//虚拟头节点法
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode prev = dummyHead;
ListNode cur = prev.next;
while(cur != null){
//引入next指针
ListNode next = cur.next;
if(next == null){
//只有一个元素
return dummyHead.next;
}
if(cur.val != next.val){
//cur不是重复节点，三指针都移动
cur = cur.next;
prev = prev.next;
}else{
//让next指针一直向后移动，直到与cur.val不相等的节点位置
while(next != null && cur.val == next.val){
next = next.next;
}
// 此时next指向了第一个不重复的元素
// 此时prev - next之间所有重复元素全部删除
prev.next = next;
cur = next;
}
}
return dummyHead.next;
}5.三數總和
力扣15題
給你一個包含n 個整數的陣列nums，判斷nums 中是否存在三個元素a，b，c ，使得a b c = 0 ？請你找出所有和為 0 且不重複的三元組。
注意：答案中不可以包含重複的三元組。
程式碼實作
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}6.分割鍊錶
力扣面試題02.04
給你一個鍊錶的頭節點head 和一個特定值x ，請你將鍊錶分隔，使得所有小於x 的節點都出現在大於或等於x 的節點之前。
你不需要 保留 每個分區中各節點的初始相對位置。
程式碼實作
public ListNode partition(ListNode head, int x) {
// 创建small和big两个小链表的头节点
ListNode smallHead = new ListNode(-1);
ListNode bigHead = new ListNode(-1);
// 按照升序插入，因此需要尾插
// 分别指向两个子链表的尾部
ListNode smallTail = smallHead;
ListNode bigTail = bigHead;
//遍历原链表，根据值放入small和big链表中
while(head != null){
if(head.val < x){
smallTail.next = head;
smallTail = head;
}else{
bigTail.next = head;
bigTail = head;
}
head = head.next;
}
bigTail.next = null;
//拼接小链表和大链表
smallTail.next = bigHead.next;
return smallHead.next;
}7.合併兩個有順序的陣列
力扣88題
給你兩個按非遞減順序排列的整數數組nums1 和nums2，另有兩個整數m 和n ，分別表示nums1 和nums2 中的元素數目。請你 合併 nums2 到 nums1 中，使合併後的陣列同樣按 非遞減順序 排列。
注意：最終，合併後陣列不應由函數傳回，而是儲存在陣列 nums1 中。為了因應這種情況，nums1 的初始長度為 m n，其中前 m 個元素表示應合併的元素，後 n 個元素為 0 ，應忽略。 nums2 的長度為 n 。
程式碼實作
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = 0, p2 = 0;
int[] sorted = new int[m + n];
int cur;
while (p1 < m || p2 < n) {
if (p1 == m) {
cur = nums2[p2++];
} else if (p2 == n) {
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for (int i = 0; i != m + n; ++i) {
nums1[i] = sorted[i];
}
}8.兩數總和—輸入有序數組
力扣167題
#給你一個下標從1 開始的整數數組numbers ，該數組已按非遞減順序排列，請你從數組中找出滿足相加之和等於目標數target 的兩個數。如果設這兩個數分別是 numbers[index1] 和 numbers[index2] ，則 1
以長度為 2 的整數陣列 [index1, index2] 的形式傳回這兩個整數的下標 index1 和 index2。
程式碼實作
public int[] twoSum(int[] numbers, int target) {
int low = 0, high = numbers.length - 1;
while (low < high) {
int sum = numbers[low] + numbers[high];
if (sum == target) {
return new int[]{low + 1, high + 1};
} else if (sum < target) {
++low;
} else {
--high;
}
}
return new int[]{-1, -1};
}9.長度最小的子數組
（力扣209）給定一個含有n 個正整數的數組和一個正整數target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0
代码实现
//滑动窗口法
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
sum += nums[end];
while (sum >= s) {
ans = Math.min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}10.排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
解题思路
通过递归实现链表归并排序，有以下两个环节：
1，分割 cut 环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）； 我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。 找到中点 slow 后，执行 slow.next = None 将链表切断。 递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。 cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。
2，合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。 双指针法合并，建立辅助ListNode h 作为头部。 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。 返回辅助ListNode h 作为头部的下个节点 h.next。
代码实现
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}以上是Java雙指標法怎麼使用的詳細內容。更多資訊請關注PHP中文網其他相關文章！
如何將Maven或Gradle用於高級Java項目管理，構建自動化和依賴性解決方案？Mar 17, 2025 pm 05:46 PM本文討論了使用Maven和Gradle進行Java項目管理，構建自動化和依賴性解決方案，以比較其方法和優化策略。
如何使用適當的版本控制和依賴項管理創建和使用自定義Java庫（JAR文件）？Mar 17, 2025 pm 05:45 PM本文使用Maven和Gradle之類的工具討論了具有適當的版本控制和依賴關係管理的自定義Java庫（JAR文件）的創建和使用。
如何使用咖啡因或Guava Cache等庫在Java應用程序中實現多層緩存？Mar 17, 2025 pm 05:44 PM本文討論了使用咖啡因和Guava緩存在Java中實施多層緩存以提高應用程序性能。它涵蓋設置，集成和績效優勢，以及配置和驅逐政策管理最佳PRA
如何將JPA（Java持久性API）用於具有高級功能（例如緩存和懶惰加載）的對象相關映射？Mar 17, 2025 pm 05:43 PM本文討論了使用JPA進行對象相關映射，並具有高級功能，例如緩存和懶惰加載。它涵蓋了設置，實體映射和優化性能的最佳實踐，同時突出潛在的陷阱。[159個字符]
Java的類負載機制如何起作用，包括不同的類載荷及其委託模型？Mar 17, 2025 pm 05:35 PMJava的類上載涉及使用帶有引導，擴展程序和應用程序類負載器的分層系統加載，鏈接和初始化類。父代授權模型確保首先加載核心類別，從而影響自定義類LOA
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
AI Hentai Generator
免費產生 AI 無盡。
熱門文章
熱工具
DVWA
Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序，非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具，幫助Web開發人員更好地理解保護網路應用程式的過程，並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞，難度各不相同。請注意，該軟體中
SublimeText3漢化版
中文版，非常好用
MantisBT
Mantis是一個易於部署的基於Web的缺陷追蹤工具，用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。
SublimeText3 英文版
推薦：為Win版本，支援程式碼提示！
mPDF
mPDF是一個PHP庫，可以從UTF-8編碼的HTML產生PDF檔案。原作者Ian Back編寫mPDF以從他的網站上「即時」輸出PDF文件，並處理不同的語言。與原始腳本如HTML2FPDF相比，它的速度較慢，並且在使用Unicode字體時產生的檔案較大，但支援CSS樣式等，並進行了大量增強。支援幾乎所有語言，包括RTL（阿拉伯語和希伯來語）和CJK（中日韓）。支援嵌套的區塊級元素（如P、DIV），
