@[TOC]
说明：本文章用于 “单链表题+数组题”
“链表”知识
双指针技巧：分两类，一类是“快慢指针”，另一类是“左右指针”
“快慢指针”：-> 解决链表问题，判断链表是否包含环
“左右指针”：-> 解决数组(字符串)问题，比如二分搜索
==快慢指针框架==：
Link method(Link head) {
Link fast,slow;
fast = slow = head;
while (fast != null && fast.next != null) {
//快指针每次前进两步
fast = fast.next.next;
//慢指针每次前进一步
slow = slow.next;
}
return slow;
}
==左右指针 - 二分搜索框架==：
一、案例说明（使用快慢指针）
==单链表节点SingleLink==
package algorithm;
import lombok.Data;
/**
* 单链表节点
*/
@Data
public class SingleLink {
int val; //节点存储的值
SingleLink next; //指向下一个节点的指针
public SingleLink(int val) {
this.val = val;
this.next = null;
}
public SingleLink(int val, SingleLink next) {
this.val = val;
this.next = next;
}
}
==main函数==
public static void main(String[] args) {
/** 有环
* 1 -> 2 -> 3 -> 4
* ↑ ↓
* ↑ ← ←
*/
SingleLink link1 = new SingleLink(1);
SingleLink link2 = new SingleLink(2);
SingleLink link3 = new SingleLink(3);
SingleLink link4 = new SingleLink(4);
link1.next = link2;
link2.next = link3;
link3.next = link4;
link4.next = link2;
//偶数个数无环单链表 6-> 7 -> 8 -> 9
SingleLink evenNumberLink = new SingleLink(6, new SingleLink(7, new SingleLink(8, new SingleLink(9, null))));
//奇数个数无环单链表 6-> 7 -> 8 -> 9 -> 10
SingleLink oddNumberLink = new SingleLink(6, new SingleLink(7, new SingleLink(8, new SingleLink(9, new SingleLink(10, null)))));
//-----------------------------------双指针技巧套路框架------------------------------------------------------
//-----------------------------------（使用快慢指针）------------------------------------------------------
//问题1.1：判断链表是否有环
// System.out.println("判断链表是否有环:" + hasCycle(link1));
//问题1.2：已知链表有环，请返回这个环的起点位置
// System.out.println("返回这个环的起点位置:" + detectCycle(link1).val);
//问题1.3：寻找无环单链表的中点，要求：如果偶数个数以左面一个节点为中点
// System.out.println("寻找偶数个数无环单链表的中点:" + returnMiddleLink(evenNumberLink).val);
// System.out.println("寻找奇数个数无环单链表的中点:" + returnMiddleLink(oddNumberLink).val);
//问题1.4：寻找无环单链表的中点，要求：如果偶数个数以右面一个节点为中点
// System.out.println("寻找偶数个数无环单链表的中点:" + returnMiddleLink2(evenNumberLink).val);
// System.out.println("寻找奇数个数无环单链表的中点:" + returnMiddleLink2(oddNumberLink).val);
//问题1.5：寻找单链表的倒数第k个元素
// System.out.println("寻找单链表的倒数第k个元素:" + reciprocalK(oddNumberLink, 2).val);
//-----------------------------------（使用左右指针）------------------------------------------------------
//问题2.1：（二分搜索）搜索数组中目标值的下标
// System.out.println(":" + binarySearch(new int[]{1,2,3,4,5}, 4));
//问题2.2：两数求和：输入一个升序排列的数组nums和一个目标值target，在nums中找到两个数相加=target，请返回这两个数的索引
// twoSum(new int[]{1, 2, 3, 4, 5}, 6);
// for (int[] arr : resList) {
// for (int item : arr) {
// System.out.print(" " + item);
// }
// System.out.println();
// }
//问题2.3：反转数组，熟悉reverse方法的内部实现
// int[] arr = new int[]{1,2,3,4,5};
// reverse(arr);
// Arrays.stream(arr).forEach(item -> System.out.print(" " + item));
}
问题1.1判断链表是否有环
//问题1.1：判断链表是否有环
public static boolean hasCycle(SingleLink head) {
SingleLink fast, slow;
//初始化快、慢指针指向头节点
fast = slow = head;
while (fast != null && fast.next != null) {
//快指针每次前进两步
fast = fast.next.next;
//慢指针每次前进一步
slow = slow.next;
//如果存在环，快、慢指针必然相遇
if (fast == slow) return true;
}
return false;
}
问题1.2：已知链表有环，请返回这个环的起点位置
==思路讲解==：
/*问题1.2：已知链表有环，请返回这个环的起点位置
* 思路：快慢指针相遇时，将快慢指针中任意一个重新指向head，然后两个指针同速前进，k-m步后就会相遇，相遇之处就是环的起点
*/
public static SingleLink detectCycle(SingleLink head) {
SingleLink fast, slow;
//初始化快、慢指针指向头节点
fast = slow = head;
while (fast != null && fast.next != null) {
//快指针每次前进两步
fast = fast.next.next;
//慢指针每次前进一步
slow = slow.next;
//如果存在环，快、慢指针必然相遇
if (fast == slow) break;
}
//先把一个指针重新指向head
slow = head;
while (slow != fast) {
//两个指针以相同的速度前进
fast = fast.next;
slow = slow.next;
}
//两个指针相遇的那个单链表节点就是环的起点
return slow;
}
问题1.3：寻找无环单链表的中点，要求：如果偶数个数以左面一个节点为中点
//问题1.3：寻找无环单链表的中点，要求：如果偶数个数以左面一个节点为中点
public static SingleLink returnMiddleLink(SingleLink head) {
SingleLink fast, slow;
//初始化快、慢指针指向头节点
fast = slow = head;
while (fast != null && fast.next != null && fast.next.next != null) {
//快指针每次前进两步
fast = fast.next.next;
//慢指针每次前进一步
slow = slow.next;
}
return slow;
}
问题1.4：寻找无环单链表的中点，要求：如果偶数个数以右面一个节点为中点
//问题1.4：寻找无环单链表的中点，要求：如果偶数个数以右面一个节点为中点
public static SingleLink returnMiddleLink2(SingleLink head) {
SingleLink fast, slow;
//初始化快、慢指针指向头节点
fast = slow = head;
while (fast != null && fast.next != null) {
//快指针每次前进两步
fast = fast.next.next;
//慢指针每次前进一步
slow = slow.next;
}
return slow;
}
问题1.5：寻找单链表的倒数第k个元素
/**
* 问题1.5：寻找单链表的倒数第k个元素
* 思路：使用快慢指针，让快指针先走k步，然后快慢指针同速前进，当快指针走到末尾null时，慢指针所在位置就是倒数第k个链表节点
* @param head 头链表节点
* @param k 倒数第k个数
* @return 节点
*/
public static SingleLink reciprocalK(SingleLink head, int k) {
SingleLink fast, slow;
fast = slow = head;
while (k-- > 0) fast = fast.next;
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
二、案例说明（使用左右指针）
问题2.1：（二分搜索）搜索数组中目标值的下标
//问题2.1：（二分搜索）搜索数组中目标值的下标
public static int binarySearch(int[] nums, int target) {
//左右指针在数组的两端初始化
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return -1;
}
问题2.2：两数求和：输入一个升序排列的数组nums和一个目标值target，在nums中找到两个数相加=target，请返回这两个数的索引
//问题2.2：两数求和：输入一个升序排列的数组nums和一个目标值target，在nums中找到两个数相加=target，请返回这两个数的索引
public static void twoSum(int[] nums, int target) {
//左右指针在数组的两端初始化
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
resList.add(new int[]{left, right});
right--;
continue;
} else if (sum < target) {
left++; //让sum大一点
} else if (sum > target) {
right--; //让sum小一点
}
}
}
问题2.3：反转数组，熟悉reverse方法的内部实现
//问题2.3：反转数组，熟悉reverse方法的内部实现
public static void reverse(int[] nums) {
//左右指针在数组的两端初始化
int left = 0;
int right = nums.length - 1;
while (left < right) {
//交换nums[left]和nums[right]
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
