双指针（逆向，快慢）
# 202. 快乐数 - 力扣（LeetCode） (opens new window)
class Solution {
public boolean isHappy(int n) {
int slow = n;
int fast = getNext(n);
while (fast != 1 && slow != fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast == 1;
}
public int getNext(int n){
int sum=0;
while (n > 0) {
int d = n % 10;
n = n / 10;
sum += d * d;
}
return sum;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 142. 环形链表 II - 力扣（LeetCode） (opens new window)
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast,slow;
fast=slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow) break;
}
if(fast==null||fast.next==null){
return null;
}
slow=head;
while(slow!=fast){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 160. 相交链表 - 力扣（LeetCode） (opens new window)
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode B = headB, A = headA;
while (A != B) {
A = A == null ? headB : A.next;
B = B == null ? headA : B.next;
}
return A;
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 21. 合并两个有序链表 - 力扣（LeetCode） (opens new window)
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dum = new ListNode(0), cur = dum;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
cur.next = list1;
list1 = list1.next;
}
else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 != null ? list1 : list2;
return dum.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 88. 合并两个有序数组 - 力扣（LeetCode） (opens new window)
class Solution {
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) {
//p1指针遍历完
if (p1 == m) {
cur = nums2[p2++];
//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];
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 倒序双指针
//倒序双指针
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1;
int tail = m + n - 1;
int cur;
while (p1 >= 0 || p2>= 0) {
if (p1 == -1) {
cur = nums2[p2--];
} else if (p2 == -1) {
cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
} else {
cur = nums2[p2--];
}
nums1[tail--] = cur;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 86. 分隔链表 - 力扣（LeetCode） (opens new window)
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode small=new ListNode(0);
ListNode smallHead=small;
ListNode large=new ListNode(0);
ListNode largeHead=large;
while(head!=null){
if(head.val<x){
small.next=head;
small=small.next;
}else{
large.next=head;
large=large.next;
}
head=head.next;
}
large.next=null;
small.next=largeHead.next;
return smallHead.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 92. 反转链表 II - 力扣（LeetCode） (opens new window)
双指针+头插法+哑节点
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummyHead = new ListNode(0);
dummyHead.next=head;
ListNode g=dummyHead;
ListNode p=dummyHead.next;
for(int step = 0;step < left - 1;step++){
g = g.next;
p = p.next;
}
for(int i = 0;i < right - left ;i++){
ListNode removed = p.next;
p.next = p.next.next;
removed.next = g.next;
g.next = removed;
}
return dummyHead.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 15. 三数之和 - 力扣（LeetCode） (opens new window)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int k = 0; k < nums.length - 2; k++) {
//当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 3 个元素都大于 0 ，在此固定指针 k 之后不可能再找到结果了
if (nums[k] > 0) break;
//当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合
if (k > 0 && nums[k] == nums[k - 1]) continue;
int i = k + 1, j = nums.length - 1;
while (i < j) {
int sum = nums[k] + nums[i] + nums[j];
if (sum < 0) {
//当s < 0时，i += 1并跳过所有重复的nums[i]；
i++;
while(i < j && nums[i] == nums[i-1]) {
i++;
}
} else if (sum > 0) {
//当s > 0时，j -= 1并跳过所有重复的nums[j]；
j--;
while(i < j && nums[j] == nums[j+1]) {
j--;
}
} else {
//当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j]，防止记录到重复组合
res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
i++;
while(i < j && nums[i] == nums[i-1]) {
i++;
}
j--;
while(i < j && nums[j] == nums[j+1]) {
j--;
}
}
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 75. 颜色分类 - 力扣（LeetCode） (opens new window)
class Solution {
public void sortColors(int[] nums) {
int p0 = 0, p2 = nums.length - 1;
for (int i = 0; i <= p2; i++) {
// 如果遍历到2，将当前位置和p2交换位置
// 注意：当我们找到2时，我们需要不断地将其与nums[p2]进行交换，直到新的nums[i]不为2
while (i <= p2 && nums[i] == 2) {
int temp = nums[i];
nums[i] = nums[p2];
nums[p2] = temp;
--p2;
}
if (nums[i] == 0) {
int temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
++p0;
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 977. 有序数组的平方 - 力扣（LeetCode） (opens new window)
class Solution {
public int[] sortedSquares(int[] nums) {
int[] res = new int[nums.length];
int left = 0, right = nums.length - 1,cur = nums.length - 1;
while (left <= right) {
if (Math.abs(nums[left]) >= Math.abs(nums[right])) {
res[cur--] = nums[left] * nums[left];
left++;
} else {
res[cur--] = nums[right] * nums[right];
right--;
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 11. 盛最多水的容器 - 力扣（LeetCode） (opens new window)
class Solution {
public int maxArea(int[] height) {
int res = 0;
int left = 0, right = height.length - 1;
while (left <= right) {
if (height[left] >= height[right]) {
res = Math.max(res,height[right] * (right - left));
right--;
} else {
res = Math.max(res,height[left] * (right - left));
left++;
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
编辑 (opens new window)
上次更新: 2025/06/13, 00:51:28