Biasanya digunakan dalam struktur data linear, seperti senarai terpaut dan tatasusunan.
Penunjuk sebenarnya ialah indeks data atau nod senarai terpaut. Dua penunjuk bergerak ke arah kiri dan kanan sehingga syarat carian dipenuhi. Penunjuk berganda boleh dibahagikan kepada penunjuk berganda dalam arah yang sama, penunjuk berganda dalam arah yang berbeza, penunjuk cepat dan perlahan, dan tingkap gelongsor. Pilih model penunjuk berganda berdasarkan keperluan anda, seperti memadamkan elemen pendua dalam tatasusunan atau senarai terpaut, penunjuk berganda dalam arah yang sama (senarai linear mesti dipesan secara amnya digunakan dalam senarai terpaut, seperti mencari); titik tengah senarai terpaut dan menentukan sama ada senarai terpaut adalah Jika terdapat gelang, tentukan titik permulaan penggantian senarai terpaut, panjang gelang dan elemen terakhir Kth senarai terpaut Contohnya, dalam perduaan carian, penunjuk berganda anisotropik digunakan; Tetingkap gelongsor sebenarnya adalah operasi pada selang tertentu tatasusunan atau senarai terpaut Sebagai contoh, cari subrentetan terpanjang/terpendek atau keperluan panjang subrentetan tertentu.
Soalan 141
Anda diberi kepala nod kepala senarai terpaut, dan tentukan sama ada terdapat kitaran dalam senarai terpaut.
Jika terdapat nod dalam senarai terpaut yang boleh dicapai semula dengan menjejaki penuding seterusnya secara berterusan, maka terdapat kitaran dalam senarai terpaut. Untuk mewakili kitaran dalam senarai terpaut yang diberikan, sistem penilaian secara dalaman menggunakan pos integer untuk mewakili kedudukan dalam senarai terpaut di mana ekor senarai terpaut disambungkan (indeks bermula dari 0). Nota: pos tidak diluluskan sebagai parameter. Hanya untuk mengenal pasti situasi sebenar senarai pautan.
Mengembalikan benar jika terdapat kitaran dalam senarai terpaut. Jika tidak, pulangkan palsu .
Pelaksanaan kod
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;
}
}Jawab 876 soalan dengan pantas
Tetapkan senarai terpaut tunggal yang tidak kosong dengan nod kepala sebagai kepala dan kembalikan nod tengah senarai terpaut.
Jika terdapat dua nod perantaraan, kembalikan nod perantaraan kedua.
Pelaksanaan kod
//快慢指针法
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;
}Selesaikan 328 soalan dengan kuat
Memandangkan nod kepala senarai pautan tunggal, gabungkan semua nod dengan indeks ganjil dan nod dengan indeks genap bersama-sama, dan kembalikan senarai yang disusun semula.
Indeks nod pertama dianggap ganjil, indeks nod kedua dianggap genap, dan seterusnya.
Pelaksanaan Kod
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;
}Hentikan 82 soalan
Memandangkan ketua senarai terpaut yang diisih, padamkan semua nod dengan nombor pendua dalam senarai terpaut asal, hanya meninggalkan nombor yang berbeza. Kembalikan senarai terpaut yang diisih
Pelaksanaan kod
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;
}Selesaikan 15 soalan dengan kuat
<. 🎜>Memberi anda nombor tatasusunan yang mengandungi n integer, tentukan sama ada terdapat tiga elemen a, b, c dalam nombor supaya a + b + c = 0? Sila cari semua tiga kali ganda tidak berulang yang jumlahnya ialah 0. Nota: Jawapan tidak boleh mengandungi pendua tiga kali ganda.
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;
}
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;
}
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];
}
}.
Anda diberi nombor tatasusunan integer dengan subskrip bermula dari 1. Tatasusunan telah disusun dalam susunan tidak menurun Sila cari dua nombor daripada tatasusunan supaya jumlahnya sama dengan sasaran nombor sasaran. Jika kedua-dua nombor ialah nombor[index1] dan nombor[index2] masing-masing, maka 1 <= indeks1 <= nombor.panjang . Mengembalikan indeks indeks1 dan indeks2 kedua-dua integer ini sebagai tatasusunan integer panjang 2 [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};
}找出该数组中满足其和 ≥ 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;
}给你链表的头结点 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;
}Atas ialah kandungan terperinci Cara menggunakan kaedah penunjuk berganda Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
