Wird normalerweise in linearen Datenstrukturen wie verknüpften Listen und Arrays verwendet.
Ein Zeiger ist eigentlich der Index von Daten oder der Knoten einer verknüpften Liste. Die beiden Zeiger bewegen sich nach links und rechts, bis die Suchbedingungen erfüllt sind. Doppelzeiger können in Doppelzeiger in die gleiche Richtung, Doppelzeiger in verschiedene Richtungen, schnelle und langsame Zeiger und Schiebefenster unterteilt werden. Wählen Sie ein Doppelzeigermodell basierend auf Ihren Anforderungen, z. B. zum Löschen doppelter Elemente in einem Array oder einer verknüpften Liste. Doppelzeiger in die gleiche Richtung (lineare Listen müssen geordnet werden) werden im Allgemeinen in verknüpften Listen verwendet, z. B. beim Suchen Der Mittelpunkt einer verknüpften Liste und die Bestimmung, ob eine verknüpfte Liste vorhanden ist. Bestimmen Sie den Startpunkt der verknüpften Liste, die Länge des Rings und das K-te letzte Element der verknüpften Liste. Beispielsweise im Binärformat Bei der Suche werden anisotrope Doppelzeiger verwendet. Das Schiebefenster ist tatsächlich eine Operation für ein bestimmtes Intervall eines Arrays oder einer verknüpften Liste. Finden Sie beispielsweise die längste/kürzeste Teilzeichenfolge oder die Längenanforderung einer bestimmten Teilzeichenfolge.
Likou 141-Frage
Geben Sie den Kopfknoten der verknüpften Liste an ob es einen Zyklus in der verknüpften Liste gibt.
Wenn es in der verknüpften Liste einen Knoten gibt, der durch kontinuierliches Verfolgen des nächsten Zeigers wieder erreicht werden kann, dann liegt in der verknüpften Liste ein Zyklus vor. Um einen Ring in einer bestimmten verknüpften Liste darzustellen, verwendet das Bewertungssystem intern die Ganzzahl pos, um die Position in der verknüpften Liste darzustellen, an der das Ende der verknüpften Liste verbunden ist (Index beginnt bei 0). Hinweis: pos wird nicht als Parameter übergeben. Nur um die tatsächliche Situation der verknüpften Liste zu identifizieren.
Wenn die verknüpfte Liste einen Ring enthält, geben Sie true zurück. Andernfalls geben Sie false zurück.
Code-Implementierung
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;
}
}
//快慢指针法
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;
}Code-Implementierung
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;
}
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;
}Sie erhalten den Kopfknoten einer verknüpften Liste und einen bestimmten Wert x. Bitte trennen Sie die verknüpfte Liste so, dass alle Knoten kleiner als x vor Knoten größer oder gleich x erscheinen.
Sie müssen die anfängliche relative Position jedes Knotens in jeder Partition nicht beibehalten. #🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜#Code -Implementierung
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;
}7. 🎜#
Sie erhalten zwei ganzzahlige Arrays nums1 und nums2, die in nicht absteigender Reihenfolge angeordnet sind, sowie zwei ganze Zahlen m und n, die die Anzahl der Elemente in nums1 bzw. nums2 darstellen. Bitte führen Sie nums2 mit nums1 zusammen, damit das zusammengeführte Array ebenfalls in nicht absteigender Reihenfolge angeordnet ist.
Hinweis: Letztendlich sollte das zusammengeführte Array nicht von der Funktion zurückgegeben, sondern im Array nums1 gespeichert werden. Um dieser Situation gerecht zu werden, hat nums1 eine Anfangslänge von m + n, wobei die ersten m Elemente Elemente darstellen, die zusammengeführt werden sollen, und die letzten n Elemente 0 sind und ignoriert werden sollten. Die Länge von nums2 beträgt n .
Code-Implementierung 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;
}#🎜🎜 #利克167question
Sie erhalten ein ganzzahliges Array mit Zahlen beginnend bei 1. Das Array wurde in nicht absteigender Reihenfolge angeordnet, sodass die Summe der Additionen dem Ziel entspricht Zahl. Die beiden Zahlen des Ziels. Wenn die beiden Zahlen Zahlen[index1] bzw. Zahlen[index2] sind, dann ist 1 <= index1 < index2 <= zahlen.länge . 
Code-Implementierung
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];
}
}9. Subarray mit der kleinsten Länge
(Likou 209) Gegeben sei ein Array mit n positiven Ganzzahlen und einem positiven Ganzzahlziel.
找出该数组中满足其和 ≥ 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;
}Das obige ist der detaillierte Inhalt vonSo verwenden Sie die Java-Doppelzeigermethode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
