二分查找
69. x 的平方根 - 力扣（LeetCode）
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
示例 2：
1
2
3
| 输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
|
提示：
答案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int mySqrt(int x) {
if (x == 0) {
return 0;
}
if (x == 1) {
return 1;
}
int i = 0, j = x / 2 + 1;
while (1 < j - i) {
int mid = (i + j) >>> 1;
if ((long) mid * mid > x) {
j = mid;
} else {
i = mid;
}
}
return i;
}
|
E01. 二分查找-力扣 704 题
要点：减而治之，可以用递归或非递归实现
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
例如
1
2
3
4
5
6
7
| 输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
|
参考答案：可以用讲过的任意一种二分求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| static int binarySearch(int[] a, int target) {
int i = 0, j = a.length;
while (1 < j - i) {
int mid = (i + j) >>> 1;
if (a[mid] < target) {
i = mid + 1;
} else {
j = mid - 1;
}
}
return a[i] == target ? i : -1;
}
|
E02. 搜索插入位置-力扣 35 题
要点：理解谁代表插入位置
给定一个排序数组和一个目标值
- 在数组中找到目标值，并返回其索引
- 如果目标值不存在于数组中，返回它将会被按顺序插入的位置
例如
1
2
3
4
5
6
7
8
| 输入: nums = [1,3,5,6], target = 5
输出: 2
输入: nums = [1,3,5,6], target = 2
输出: 1
输入: nums = [1,3,5,6], target = 7
输出: 4
|
参考答案1：用二分查找基础版代码改写，基础版中，找到返回 m，没找到 i 代表插入点，因此有
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int searchInsert(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
return m;
}
}
return i;
}
|
参考答案2：用二分查找平衡版改写，平衡版中
- 如果 target == a[i] 返回 i 表示找到
- 如果 target < a[i]，例如 target = 2，a[i] = 3，这时就应该在 i 位置插入 2
- 如果 a[i] < target，例如 a[i] = 3，target = 4，这时就应该在 i+1 位置插入 4
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static int searchInsert(int[] a, int target) {
int i = 0, j = a.length;
while (1 < j - i) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m;
} else {
i = m;
}
}
return (target <= a[i]) ? i : i + 1;
}
|
参考答案3：用 leftmost 版本解，返回值即为插入位置（并能处理元素重复的情况）
1
2
3
4
5
6
7
8
9
10
11
12
| public int searchInsert(int[] a, int target) {
int i = 0, j = a.length - 1;
while(i <= j) {
int m = (i + j) >>> 1;
if(target <= a[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i;
}
|
E03. 搜索开始结束位置-力扣 34 题
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题
例如
1
2
3
4
5
6
7
8
| 输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
输入：nums = [], target = 0
输出：[-1,-1]
|
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
42
| public static int left(int[] a, int target) {
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m;
j = m - 1;
}
}
return candidate;
}
public static int right(int[] a, int target) {
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m;
i = m + 1;
}
}
return candidate;
}
public static int[] searchRange(int[] nums, int target) {
int x = left(nums, target);
if(x == -1) {
return new int[] {-1, -1};
} else {
return new int[] {x, right(nums, target)};
}
}
|
递归 - single recursion
E03. 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public static int recursion(int[] a, int target, int i, int j) {
if (i > j) {
return -1;
}
int m = (i + j) >>> 1;
if (target < a[m]) {
return recursion(a, target, i, m - 1);
} else if (a[m] < target) {
return recursion(a, target, m + 1, j);
} else {
return m;
}
}
public int search(int[] nums, int target) {
return recursion(nums, target, 0, nums.length - 1);
}
}
|
E04. 冒泡排序
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
| public static void main(String[] args) {
int[] a = {3, 2, 6, 1, 5, 4, 7};
bubble(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
private static void bubble(int[] a, int low, int high) {
if (low == high) {
return;
}
int j = low;
for (int i = low; i < high; i++) {
if (a[i] > a[i + 1]) {
int temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
j=i;
}
}
bubble(a,low,j);
}
|
- low 与 high 为排序范围
- j 表示的是未排序的边界，下一次递归时的 high
- 发生交换，意味着有无序情况
- 最后一次交换（以后没有无序）时，左侧 i 仍是无序，右侧 i+1 已然有序
E05. 插入排序
版本v1
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
| public static void main(String[] args) {
int[] a = {3, 2, 6, 1, 5, 7, 4};
insertion(a, 1);
System.out.println(Arrays.toString(a));
}
private static void insertion(int[] a, int low) {
if (low == a.length) return;
int t = a[low];
int i = low - 1;
while (i >= 0 && a[i] > t) {
a[i + 1] = a[i];
i--;
}
if (i + 1 != low) {
a[i + 1] = t;
}
insertion(a, low + 1);
}
|
已排序区域：[0 .. i .. low-1]
未排序区域：[low .. high]
版本v2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public static void main(String[] args) {
int[] a = {3, 2, 6, 1, 5, 7, 4};
insertion(a, 1, a.length - 1);
System.out.println(Arrays.toString(a));
}
private static void insertion(int[] a, int low, int high) {
if (low > high) {
return;
}
int t = a[low];
int i = low - 1;
while (i >= 0 && a[i] > t) {
a[i + 1] = a[i];
i--;
}
if(i + 1 != low) {
a[i + 1] = t;
}
insertion(a, low + 1, high);
}
|
- 第一块代码是只考虑 low 边界的情况，参考以上代码，理解 low-1 .. high 范围内的处理方法
- 扩展：利用二分查找 leftmost 版本，改进寻找插入位置的代码
另一种插入排序的实现,缺点: 赋值次数较多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| private static void insertion2(int[] a, int low) {
if (low == a.length) {
return;
}
int i = low - 1;
while (i >= 0 && a[i] > a[i + 1]) {
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
i--;
}
insertion(a, low + 1);
}
|
E06. 约瑟夫问题[^16]
待完成！！！
递归 - multi recursion
E02. 汉诺塔[^13]
Tower of Hanoi，是一个源于印度古老传说：大梵天创建世界时做了三根金刚石柱，在一根柱子从下往上按大小顺序摞着 64 片黄金圆盘，大梵天命令婆罗门把圆盘重新摆放在另一根柱子上，并且规定
下面的动图演示了4片圆盘的移动方法
使用程序代码模拟圆盘的移动过程，并估算出时间复杂度
思路
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
42
43
44
45
46
47
48
49
50
51
52
| public class E02HanoiTower {
static LinkedList<Integer> a = new LinkedList<>();
static LinkedList<Integer> b = new LinkedList<>();
static LinkedList<Integer> c = new LinkedList<>();
public static void main(String[] args) {
StopWatch sw = new StopWatch();
int n = 4;
init(n);
sw.start("n="+n);
move(n,a,b,c);
sw.stop();
print();
System.out.println(sw.prettyPrint());
}
static void move(int n, LinkedList<Integer> a, LinkedList<Integer> b, LinkedList<Integer> c) {
if (n == 0) return;
move(n - 1, a, c, b);
c.addLast(a.removeLast());
move(n - 1, b,a, c);
}
static void init(int n) {
for (int i = 1; i <= n; i++) {
a.add(i);
}
}
private static void print() {
System.out.println("******************************");
System.out.println(a);
System.out.println(b);
System.out.println(c);
}
}
|
E03. 杨辉三角[^6]
分析
把它斜着看
1
2
3
4
5
| 1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
|
1 8
1 1 6 (n-i-1)*2
1 2 1 4
1 3 3 1 2
1 4 6 4 1 0
- 行 $i$，列 $j$，那么 $[i][j]$ 的取值应为 $[i-1][j-1] + [i-1][j]$
- 当 $j=0$ 或 $i=j$ 时，$[i][j]$ 取值为 $1$
题解
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
| public static void print(int n) {
for (int i = 0; i < n; i++) {
if (i < n - 1) {
System.out.printf("%" + 2 * (n - 1 - i) + "s", " ");
}
for (int j = 0; j < i + 1; j++) {
System.out.printf("%-4d", element(i, j));
}
System.out.println();
}
}
public static int element(int i, int j) {
if (j == 0 || i == j) {
return 1;
}
return element(i - 1, j - 1) + element(i - 1, j);
}
public static void printSpace(int n) {
for (int i = 0; i < n; i++) {
System.out.print(" ");
}
}
|
优化1
是 multiple recursion，因此很多递归调用是重复的，例如
- recursion(3, 1) 分解为
- recursion(2, 0) + recursion(2, 1)
- 而 recursion(3, 2) 分解为
- recursion(2, 1) + recursion(2, 2)
这里 recursion(2, 1) 就重复调用了，事实上它会重复很多次，可以用 static AtomicInteger counter = new AtomicInteger(0) 来查看递归函数的调用总次数
事实上，可以用 memoization 来进行优化：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public static void print1(int n) {
int[][] triangle = new int[n][];
for (int i = 0; i < n; i++) {
triangle[i] = new int[i + 1];
for (int j = 0; j <= i; j++) {
System.out.printf("%-4d", element1(triangle, i, j));
}
System.out.println();
}
}
public static int element1(int[][] triangle, int i, int j) {
if (triangle[i][j] > 0) {
return triangle[i][j];
}
if (j == 0 || i == j) {
triangle[i][j] = 1;
return triangle[i][j];
}
triangle[i][j] = element1(triangle, i - 1, j - 1) + element1(triangle, i - 1, j);
return triangle[i][j];
}
|
- 将数组作为递归函数内可以访问的遍历，如果 $triangle[i][j]$ 已经有值，说明该元素已经被之前的递归函数计算过，就不必重复计算了
优化2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static void print2(int n) {
int[] row = new int[n];
for (int i = 0; i < n; i++) {
createRow(row, i);
for (int j = 0; j <= i; j++) {
System.out.printf("%-4d", row[j]);
}
System.out.println();
}
}
private static void createRow(int[] row, int i) {
if (i == 0) {
row[0] = 1;
return;
}
for (int j = i; j > 0; j--) {
row[j] = row[j - 1] + row[j];
}
}
|
注意：还可以通过每一行的前一项计算出下一项，不必借助上一行，这与杨辉三角的另一个特性有关，暂不展开了
链表
E01. 反转单向链表-力扣 206 题
对应力扣题目 206. 反转链表 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
| 输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
输入：[1,2]
输出：[2,1]
输入：[]
输出：[]
|
方法1
构造一个新链表，从旧链表依次拿到每个节点，创建新节点添加至新链表头部，完成后新链表即是倒序的
1
2
3
4
5
6
7
8
9
10
| public ListNode reverseList(ListNode o1) {
ListNode n1 = null;
ListNode p = o1;
while (p != null) {
n1 = new ListNode(p.val, n1);
p = p.next;
}
return n1;
}
|
评价：简单直白，就是得新创建节点对象
方法2
与方法1 类似，构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成后新链表即是倒序的，区别在于原题目未提供节点外层的容器类，这里提供一个，另外一个区别是并不去构造新节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| static class List {
ListNode head;
public List(ListNode head) {
this.head = head;
}
public ListNode removeFirst(){
ListNode first = head;
if (first != null) {
head = first.next;
}
return first;
}
public void addFirst(ListNode first) {
first.next = head;
head = first;
}
}
|
代码
1
2
3
4
5
6
7
8
9
| public ListNode reverseList(ListNode head) {
List list1 = new List(head);
List list2 = new List(null);
ListNode first;
while ((first = list1.removeFirst()) != null) {
list2.addFirst(first);
}
return list2.head;
}
|
评价：更加面向对象，如果实际写代码而非刷题，更多会这么做
方法3
递归，在归时让 $5 \rightarrow 4$，$4 \rightarrow 3$ …
首先，写一个递归方法，返回值用来拿到最后一个节点
1
2
3
4
5
6
7
| public ListNode reverseList(ListNode p) {
if (p == null || p.next == null) {
return p;
}
ListNode last = reverseList(p.next);
return last;
}
|
- 注意1：递归终止条件是 curr.next == null，目的是到最后一个节点就结束递归，与之前递归遍历不一样
- 注意2：需要考虑空链表即 p == null 的情况
可以先测试一下
1
2
3
4
5
6
7
| ListNode o5 = new ListNode(5, null);
ListNode o4 = new ListNode(4, o5);
ListNode o3 = new ListNode(3, o4);
ListNode o2 = new ListNode(2, o3);
ListNode o1 = new ListNode(1, o2);
ListNode n1 = new E01Leetcode206().reverseList(o1);
System.out.println(n1);
|
会打印
下面为伪码调用过程，假设节点分别是 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$，先忽略返回值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| reverseList(ListNode p = 1) {
reverseList(ListNode p = 2) {
reverseList(ListNode p = 3) {
reverseList(ListNode p = 4) {
reverseList(ListNode p = 5) {
if (p == null || p.next == null) {
return p;
}
}
}
}
}
}
|
接下来，从 p = 4 开始，要让 $5 \rightarrow 4$，$4 \rightarrow 3$ …
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| reverseList(ListNode p = 1) {
reverseList(ListNode p = 2) {
reverseList(ListNode p = 3) {
reverseList(ListNode p = 4) {
reverseList(ListNode p = 5) {
if (p == null || p.next == null) {
return p;
}
}
}
}
}
}
|
最终代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
|
Q：为啥不能在递的过程中倒序？
A：比如
- $ 1 \rightarrow 2 \rightarrow 3 $ 如果递的过程中让 $2 \rightarrow 1$ 那么此时 $2 \rightarrow 3$ 就被覆盖，不知道接下来递给谁
- 而归的时候让 $3 \rightarrow 2$ 不会影响上一层的 $1 \rightarrow 2$
评价：单向链表没有 prev 指针，但利用递归的特性【记住了】链表每次调用时相邻两个节点是谁
方法4
从链表每次拿到第二个节点，将其从链表断开，插入头部，直至它为 null 结束
- 设置指针 o1(旧头)、n1(新头)、o2(旧老二)，分别指向第一，第一，第二节点
$\frac{n1 \ o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$
- 将 o2 节点从链表断开，即 o1 节点指向第三节点
$ \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$ ，$\frac{o2}{2}$
- o2 节点链入链表头部，即
$\frac{o2}{2} \rightarrow \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$
- n1 指向 o2
$\frac{n1 \ o2}{2} \rightarrow \frac{o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$
- o2 指向 o1 的下一个节点，即
$\frac{n1}{2} \rightarrow \frac{o1}{1} \rightarrow \frac{o2}{3} \rightarrow 4 \rightarrow 5 \rightarrow null$
重复以上 $2\sim5$ 步，直到 o2 指向 null
还应当考虑边界条件，即链表中不满两个元素时，无需走以上逻辑
参考答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public ListNode reverseList(ListNode o1) {
if (o1 == null || o1.next == null) {
return o1;
}
ListNode o2 = o1.next;
ListNode n1 = o1;
while (o2 != null) {
o1.next = o2.next;
o2.next = n1;
n1 = o2;
o2 = o1.next;
}
return n1;
}
|
方法5
要点：把链表分成两部分，思路就是不断从链表2的头，往链表1的头搬移
- n1 指向 null，代表新链表一开始没有元素，o1 指向原链表的首节点
$\frac{n1}{null}$，$\frac{o1}{1} \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$
- 开始循环，o2 指向原链表次节点
$\frac{n1}{null}$，$\frac{o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$
- 搬移
$\frac{o1}{1} \rightarrow \frac{n1}{null}$ ， $\frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$
- 指针复位
$\frac{n1}{1} \rightarrow null$ ， $\frac{o1 \ o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$
- 重复 $2\sim4$ 步
- 当 o1 = null 时退出循环
参考答案
1
2
3
4
5
6
7
8
9
10
11
12
13
| public ListNode reverseList(ListNode o1) {
if (o1 == null || o1.next == null) {
return o1;
}
ListNode n1 = null;
while (o1 != null) {
ListNode o2 = o1.next;
o1.next = n1;
n1 = o1;
o1 = o2;
}
return n1;
}
|
评价：本质上与方法2 相同，只是方法2更为面向对象题
例如
1
2
3
4
5
6
7
8
| 输入：head = [1,2,6,3,6], val = 6
输出：[1,2,3]
输入：head = [], val = 1
输出：[]
输入：head = [7,7,7,7], val = 7
输出：[]
|
E03. 删除倒数节点-力扣 19 题
例如
1
2
3
4
5
6
7
8
| 输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
输入：head = [1], n = 1
输出：[]
输入：head = [1,2], n = 1
输出：[1]
|
另外题目提示
解法一
写一个递归方法，得到倒数的次序。
1
2
3
4
5
6
7
8
9
10
11
| static int recursion(ListNode p, int n) {
if (p == null) {
return 0;
}
int nth = recursion(p.next, n);
System.out.println("nth:"+nth+"\t p:"+p.toString());
if (nth == n) {
p.next = p.next.next;
}
return nth + 1;
}
|
1
2
3
4
5
6
7
|
nth是倒数的次序 p为当前节点
nth:0 p:[5]
nth:1 p:[4,5]
nth:2 p:[3,4,5]
nth:3 p:[2,3,4,5]
nth:4 p:[1,2,4,5]
|
当nth==n时 p为要删除节点的上一个，删除节点即可。
但上述代码有一个问题，就是若删除的是第一个节点，它没有上一个节点，因此可以加一个哨兵来解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode sentinel = new ListNode(-1, head);
recursion(sentinel, n);
return sentinel.next;
}
public int recursion(ListNode p, int n) {
if (p == null) {
return 0;
}
int nth = recursion(p.next, n);
if (nth == n) {
p.next = p.next.next;
}
return nth + 1;
}
|
解法二
快慢指针，p1 指向待删节点的上一个，p2 先走 n + 1 步
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| i=0
p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null
i=1
p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null
i=2
p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null
i=3 从此开始 p1 p2 依次向右平移, 直到 p2 移动到末尾
p1 p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null
p1 p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode s = new ListNode(-1, head);
ListNode p1 = s;
ListNode p2 = s;
for (int i = 0; i < n + 1; i++) {
p2 = p2.next;
}
while (p2 != null) {
p1 = p1.next;
p2 = p2.next;
}
p1.next = p1.next.next;
return s.next;
}
|
这个方法中，使用了两个指针p1和p2来定位要删除的节点。首先，p2指针先向后移动n+1步，使得p1和p2之间的距离为n+1。然后，同时移动p1和p2指针，直到p2指针到达链表末尾。这样，p1指针就指向了要删除节点的前一个节点。
接下来，将p1的next指针指向要删除节点的下一个节点，即完成了删除操作。最后，返回头节点的next指针，即为删除节点后的链表。
由于p2指针先向后移动了n+1步，所以p1指针和p2指针之间的距离为n+1。因此，当p2指针到达链表末尾时，p1指针正好指向要删除节点的前一个节点。这样，通过移动p1指针的next指针，就可以删除要删除的节点。
E04. 有序链表去重-力扣 83 题
例如
1
2
3
4
5
| 输入：head = [1,1,2]
输出：[1,2]
输入：head = [1,1,2,3,3]
输出：[1,2,3]
|
注意：重复元素保留一个
E05. 有序链表去重-力扣 82 题
例如
1
2
3
4
5
| 输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
输入：head = [1,1,1,2,3]
输出：[2,3]
|
注意：重复元素一个不留
E06. 合并有序链表-力扣 21 题
例
1
2
3
4
5
6
7
8
| 输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
输入：l1 = [], l2 = []
输出：[]
输入：l1 = [], l2 = [0]
输出：[0]
|
E07. 合并多个有序链表-力扣 23 题
例
1
2
3
4
5
6
7
8
9
10
| 输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
|
E08. 查找链表中间节点-力扣 876 题
例如
1
2
3
4
5
| 输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
|
数组
E01. 合并有序数组
将数组内两个区间内的有序元素合并
例
可以视作两个有序区间
1
| [1, 5, 6] 和 [2, 4, 10, 11]
|
合并后，结果仍存储于原有空间
队列
栈
双端队列
优先级队列
堆
二叉树
