街蝉

41-53. 最大子数组和【中等】

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组&nbsp;[4,-1,2,1] 的和最大，为&nbsp;6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

解法思路及注意点

这道题可以是简单的思路，也可以用dp，但是dp会超时，显然不如下面的解法，但其实核心也是dp的思路

无非就是dp[i]表示从0~i的前缀和，但是又不需要把所有的数都求出来，因为我们知道

如果当前前缀和是负数，那么相加一定会让当前指向的数更小
只有当前前缀和是正数，相加才会让当前指向的数更大，而我们想要的结果就是最大的，所以可以省下很多次没用的计算

如果当前前缀和已经是负数，那么就从下一个下标做为子数组的开头

最终代码

java

public int maxSubArray(int[] nums) {
	int n = nums.length;
	if (n == 0) return 0;

	int maxSum = nums[0]; // 最大子数组和
	int curSum = nums[0]; // 当前子数组和

	for (int i = 1; i < n; i++) {
		// 如果当前子数组和小于0，则抛弃当前子数组，从nums[i]重新开始
		if (curSum < 0) {
			curSum = nums[i];
		} else {
			// 否则，将nums[i]加入当前子数组
			curSum += nums[i];
		}
		// 更新最大子数组和
		maxSum = Math.max(maxSum, curSum);
	}

	return maxSum;
}

42-56. 合并区间【中等】

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

解法思路及注意点

这道题比较简单，按左区间排序以后，（其实右区间也不需要排序了，反正是要合并的），判断当前区间的左区间curL和目前维护的区间的右区间r的关系，如果curL <= r,那么可以合并，且合并后的右区间 curR = max(curR, r) ；如果curL > r，那就说明无法合并，直接加入结果即可

下面的代码主要是学几个API，总是忘记

自定义排序

java

Arrays.sort(intervals, (o1, o2) -> {
		if (o1[0] == o2[0]) {
			return Integer.compare(o1[1], o2[1]); // 左区间相同，按右区间升序排序
		}
		return Integer.compare(o1[0], o2[0]); // 按左区间升序排序
	});

数组和list的转换

java

// 将 List<int[]> 转换为 int[][]
	int[][] res = new int[resList.size()][];
	return resList.toArray(res);

最终代码

java

public int[][] merge(int[][] intervals) {
	// 对输入数组按照左区间升序排序，如果左区间相同则按右区间升序排序
	Arrays.sort(intervals, (o1, o2) -> {
		if (o1[0] == o2[0]) {
			return Integer.compare(o1[1], o2[1]); // 左区间相同，按右区间升序排序
		}
		return Integer.compare(o1[0], o2[0]); // 按左区间升序排序
	});

	int l = intervals[0][0];
	int r = intervals[0][1];
	List<int[]> resList = new ArrayList<>();

	for (int i = 1; i < intervals.length; i++) {
		int curL = intervals[i][0];
		int curR = intervals[i][1];
		if (curL <= r) {
			// 可以合并区间，更新右边界
			r = Math.max(r, curR);
		} else {
			// 不能合并，将当前区间加入结果
			resList.add(new int[] { l, r });
			l = curL;
			r = curR;
		}
	}

	// 将最后一个区间加入结果
	resList.add(new int[] { l, r });

	// 将 List<int[]> 转换为 int[][]
	int[][] res = new int[resList.size()][];
	return resList.toArray(res);
}

43-73. 矩阵置零【中等】

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

解法思路及注意点

这道题很简单，遍历原来的矩阵matrix[i][j]找到零的时候就说明第i行第j列全都是零，添加一个标志位，第二次循环的时候处理即可

最终代码

java

public void setZeroes(int[][] matrix) {
	int m = matrix.length;
	int n = matrix[0].length;
	boolean[][] flag = new boolean[m][n];
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			if(matrix[i][j] == 0){
				// 找到0
				flag[i][j] = true;
			}
		}
	}
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			if(flag[i][j]){
				// 表示第i行和第j列所有元素都是0
				for(int k = 0; k < m; k++){
					matrix[k][j] = 0;
				}
				for(int l = 0; l < n; l++){
					matrix[i][l] = 0;
				}
			}
		}
	}
}

44-54. 螺旋矩阵【中等】

解法思路及注意点

这种题型感觉写会一遍就很好写了，关键在于拆分逻辑，要把循环的时候每一步在操作哪一行或者哪一列设计好

这道题目我们学到的一个最好的技巧是：将循环结束的条件控制为结果集是否包含了矩阵中的所有元素，这样便于控制循环结束

其次，对于螺旋矩阵遍历问题，是按照“圈数”来指定的，由外层逐渐向内层递进，如下图所示我们设计了边界

在一圈中边界值的设定如上图，很容易发现向内缩进的关键在于当前在第几圈，因此，这四个值的设定由当前循环的圈数step决定

有了上面四个特定值，显然循环一圈需要四步，即

从左到右
从上到下
从右到左
从下到上

只需要根据我们给的特定值作为边界处理即可，详细如下代码

最终代码

java

public List<Integer> spiralOrder(int[][] matrix) {
	// 循环结束条件设定为全部元素已经遍历过，简化结束条件
	int m = matrix.length;
	int n = matrix[0].length;
	int size = m * n;
	List<Integer> res = new ArrayList<>();
	// 定义循环的次数，即矩阵的圈数
	int step = 0;
	while (res.size() < size) {
		// 只要结果集数量不够，就执行下面的任务
		process(matrix, res, step++);
	}
	return res;
}

// 处理
public void process(int[][] matrix, List<Integer> res, int step) {
	int m = matrix.length;
	int n = matrix[0].length;

	// 定义上下左右边界，便于循环条件处理
	int left = step;
	int right = n - 1 - step;
	int top = step;
	int bottom = m - 1 - step;

	// 循环处理上边界，右边界，下边界以及左边界
	for (int i = left; i <= right && res.size() < m * n; i++) {
		res.add(matrix[top][i]);
	}
	for (int i =  top + 1; i <= bottom && res.size() < m * n; i++) {
		res.add(matrix[i][right]);
	}
	for (int i = right - 1; i >= left && res.size() < m * n; i--) {
		res.add(matrix[bottom][i]);
	}
	for (int i = bottom - 1; i >= top + 1 && res.size() < m * n; i--) {
		res.add(matrix[i][left]);
	}
}

45-48. 旋转图像【中等】

解法思路及注意点

这道题可以有两种解法

解法一：利用矩阵的特性，通过对称性解决旋转问题题目要求顺时针旋转九十度，可以有多种对称性解决的顺序，这里提供一种先水平反转，即对矩阵一条水平的对称轴反转，然后按照主对角线作为对称轴反转，就实现了顺时针旋转九十度，详细代码如下
解法二：真·旋转图像如果说解法一没有旋转的灵魂，这里提供了直接意义上的旋转，如下图所示，看图就很好理解但是还需要主要理解两个关键点，
- 既然是旋转，那就是互相替换，所以不管从哪一个位置作为旋转的起点都是可以的
- 旋转的次数：for (int i = 0; i < (n + 1) / 2; i++)关键是为什么➕1，如下：

对于一个 n x n 的矩阵，旋转操作可以看作从外层到内层逐层处理。每一层是一个“环”，需要独立旋转。

如果 n 是偶数，矩阵可以完全分成 n / 2 层。
如果 n 是奇数，矩阵的中心点不需要旋转，因此只需要处理 (n + 1) / 2 - 1 层。
所以为了不管是奇数还是偶数都能涵盖到正确处理的次数，还是选择了(n + 1) / 2，对于奇数的时候多出来的那个一就是中心点，操作的时候不会受到影响，所以可以直接写作 (n + 1) / 2

最终代码

java

// 解法一
public void rotate(int[][] matrix) {
	int n = matrix.length;
	// 水平翻转
	for (int i = 0; i < n / 2; ++i) {
		for (int j = 0; j < n; ++j) {
			int temp = matrix[i][j];
			matrix[i][j] = matrix[n - i - 1][j];
			matrix[n - i - 1][j] = temp;
		}
	}
	// 主对角线翻转
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			int temp = matrix[i][j];
			matrix[i][j] = matrix[j][i];
			matrix[j][i] = temp;
		}
	}
}

// 解法二
public void rotate(int[][] matrix) {
	int n = matrix.length;
	for (int i = 0; i < (n + 1) / 2; i++) {
		for (int j = 0; j < n / 2; j++) {
			// 保存当前元素
			int temp = matrix[i][j];
			// 将左下角元素移动到左上角
			matrix[i][j] = matrix[n - j - 1][i];
			// 将右下角元素移动到左下角
			matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
			// 将右上角元素移动到右下角
			matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
			// 将左上角元素移动到右上角
			matrix[j][n - i - 1] = temp;
		}
	}
}

46-240. 搜索二位矩阵II【中等】

编写一个高效的算法来搜索 n x m 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

解法思路及注意点

满足该特性，其实就是一颗二叉搜索树，选择一个起点，因为题目只能选择左下角或者右上角，随便选一个即可

最终代码

java

public boolean searchMatrix(int[][] matrix, int target) {
	int m = matrix.length;
	int n = matrix[0].length;
	// 从左下角或者右上角开始都行，这里选择左下角当做起点
	int curX = m - 1, curY = 0;
	while (curX >= 0 && curY < n) {
		if(matrix[curX][curY] == target){
			return true;
		}else if(matrix[curX][curY] < target){
			curY++;
		}else{
			curX--;
		}
	}
	return false;
}

47-160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交**：** 题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。 自定义评测：评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

解法思路及注意点

理解相交的意思，如果两条单链表相交了，那么两条链表遍历到最后一个节点一定是同一个

记录两条链表的长度，其实我们需要做的就是让两条链表都从距离相交节点相等的距离起步

当指向同一个节点时，就是相交节点了

如何保证“从距离相交节点相等的距离起步”？

如果相交的话，两条链表长度的差值就是两个头节点距离交点的距离的差值

最终代码

java

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	ListNode currA = headA;
	ListNode currB = headB;
	int countA = 1, countB = 1;
	while (currA.next != null) {
		currA = currA.next;
		countA++;
	}
	while (currB.next != null) {
		currB = currB.next;
		countB++;
	}
	// 此时A和B已经遍历到最后一个节点处
	if (currB != currA) {
		return null;
	}
	// 表示相交了
	int diff = Math.abs(countA - countB);
	if (countA > countB) {
		currA = headA;
		currB = headB;
		while (diff > 0) {
			currA = currA.next;
			diff--;
		}
	} else {
		currB = headB;
		currA = headA;
		while (diff > 0) {
			currB = currB.next;
			diff--;
		}
	}
	// 已经在距离相交节点相同距离处
	while (currA != currB) {
		currA = currA.next;
		currB = currB.next;
	}
	// 指向同一个节点
	return currA;
}

48-206. 反转链表【核心】

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解法思路及注意点

反转链表是链表基础题目，需要先把待反转链表的头节点和已经反转的链表头节点保存，然后遍历待反转链表即可

最终代码

java

public ListNode reverseList(ListNode head) {
	// 初始化两个指针：
	// - reversedHead: 指向已经反转部分的头节点，初始为 null
	ListNode reversedHead = null;

	// 遍历原始链表，逐个反转节点
	while (head != null) {
		// 1. 保存当前节点的下一个节点，防止丢失
		nextNode = head.next;

		// 2. 将当前节点的 next 指向已经反转部分的头节点
		head.next = reversedHead;

		// 3. 更新已经反转部分的头节点为当前节点
		reversedHead = head;

		// 4. 将当前节点移动到下一个节点，继续处理
		head = nextNode;
	}

	// 返回反转后的链表头节点
	return reversedHead;
}

49-234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解法思路及注意点

结合“206.反转链表”，回文结构是我们很熟悉的结构，其实说白了就是对称的一条链表，我们要做的是先找到中点，因此遍历一遍得到链表长度，即可得到中点的位置

得到重点以后有两种做法：

比较简单的，直接从开头到中点，将节点压入栈中，然后从中点起，一边遍历一遍出栈，只要不匹配就说明不符合
思路其实和上面用栈的操作一样，不过我们借鉴反转链表，再一次熟悉一下反转链表的操作思路，把中点以后的节点反转得到反转后的头节点，这样只需要让head和这个反转后的头节点一起遍历，一旦不一致说明不符合

最终代码

java

/**
 * 判断是否是回文链表
 * 首先记录整个链表的长度，然后将后半个链表反转
 * 这样从反转后的头结点和前半个的链表的头结点同时判断
 * 一旦有不一样的，就说明不是回文链表
 */
public boolean isPalindrome(ListNode head) {
	int count = 0;
	ListNode curr = head;
	while (curr != null) {
		curr = curr.next;
		count++;
	}
	count /= 2;
	curr = head;
	while (count > 0) {
		count--;
		curr = curr.next;
	}
	// 从一半起反转链表
	ListNode reverse = reverse(curr);
	// 一起从头结点开始遍历
	while (reverse != null) {
		if (reverse.val != head.val) {
			return false;
		}
		reverse = reverse.next;
		head = head.next;
	}
	return true;
}

/**
 * 反转链表
 */
private ListNode reverse(ListNode head) {
	ListNode temp;
	ListNode lastNode = null;
	while (head != null) {
		temp = head.next;
		head.next = lastNode;
		lastNode = head;
		head = temp;
	}
	// 当while循环结束的时候head为null，而lastNode指向反转后链表的头结点
	return lastNode;
}

50-141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。**注意：pos 不作为参数进行传递 **。仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。否则，返回 false 。

解法思路及注意点

判断链表是否有环，我们先理解什么是有环，当链表结构有环的时候，遍历永远停不下来，因为next一直不为空

这就想起双指针中经常做的，设置快慢指针，但是我们给快慢指针设置一步的差距 ，即慢指针比快指针一次移动慢一个单位，这样的话，一旦有环结构，快慢指针一定会在某一个节点处相遇；否则永远不会相遇

最终代码

java

public boolean hasCycle(ListNode head) {
	if(head == null || (head != null && head.next == null)){
		return false;
	}

	ListNode fast = head;
	ListNode slow = head;

	while(fast != null && fast.next != null){
		fast = fast.next.next;
		slow = slow.next;
		if(fast == slow){
			return true;
		}
	}
	return false;
}

51-142. 环形链表II【中等】

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

解法思路及注意点

这道题目首先要141的判断是否有环，操作一致

在判断有环以后，这里有一点就是如何判断入环点，记住就好

“快慢指针的相遇点，此时让慢指针归位head，使得fast和slow一步一步移动，直到再次相遇，这个相遇点就是入环的点”

最终代码

java

// 先判断有环无欢，同141
public ListNode detectCycle(ListNode head) {
	if (head == null) {
		return null;
	}

	ListNode slow = head;
	ListNode fast = head;
	boolean flag = false;

	while (fast != null && fast.next != null) {
		fast = fast.next.next;
		slow = slow.next;
		if (fast == slow) {
			flag = true;
			break;
		}
	}
	if (flag) {
		// 此时让slow归位，和fast一起一步一步，到相同引用的时候就是结果
		slow = head;
		while (slow != fast) {
			slow = slow.next;
			fast = fast.next;
		} 
		// 此时slow和fast指向的就是入环的点
		return slow;
	}
	return null;
}

52-21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1： 合并两个有序链表

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

解法思路及注意点

和“合并两个有序数组”一样，只不过改成了链表的方式

最终代码

java

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
	if(list1 == null) return list2;
	if(list2 == null) return list1;

	ListNode head;
	if(list1.val <= list2.val){
		head = list1;
		list1 = list1.next;
	}else {
		head = list2;
		list2 = list2.next;
	}
	ListNode cur = head;
	// 遍历
	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;
	}
	// 这个时候肯定有一个为空。但是不知道是谁，只有把后面的节点给他就行
	if(list1 == null){
		cur.next = list2;
	}else{
		cur.next = list1;
	}
	return head;
}

53-2. 两数相加【中等】

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1： 两数相加

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

解法思路及注意点

这道题值得去看，主要是循环执行的条件设计的很好，只要满足：当前仍然有节点不为空，或者还有进位没有计算，那就要执行，别忘了考虑进位以及所有位都计算成功只剩下进位的情况

最终代码

java

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode root = new ListNode();
	ListNode curr = root;
	int carry = 0;
	// 循环中已经包括了节点都空但是还有进位的情况
	while (l1 != null || l2 != null || carry != 0) {
		int currV = (l1 == null ? 0 : l1.val)
				+ (l2 == null ? 0 : l2.val)
				+ carry;
		if (currV > 9) {
			currV -= 10;
			carry = 1;
		} else {
			carry = 0;
		}
		curr.next = new ListNode(currV);
		curr = curr.next;
		// 移动l1和l2的逻辑
		if (l1 != null) {
			l1 = l1.next;
		}
		if (l2 != null) {
			l2 = l2.next;
		}
	}
	// ListNode root = new ListNode();因为一开始root赋值不是根据l1和l2算的，单纯是创建了一个新节点，他不能算
	return root.next;
}

54-19. 删除链表的倒数第N个节点【中等】

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1： 删除链表的倒数第N个节点

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

解法思路及注意点

做这道题目之前，我们要注意，因为要删除的节点很可能是第一个节点，如果删掉了我们就没法返回了，所以这种题目一般都要自己先设置一个 虚拟头节点，目的只是为了返回结果更方便。

如下图，我们需要“比一把尺子”走，倒数第N个节点，我们就可以先让一个快指针往后走N次，然后慢指针从开头开始，和快指针一起走，直到快指针走到了最后一个节点，那么此时慢指针就指向了待删除节点的前一个位置，此时可以直接删除，如下图

最终代码

java

public ListNode removeNthFromEnd(ListNode head, int n) {
	ListNode newHead = new ListNode(-1, head);
	// 快指针先移动n次，然后快慢指针一起，等到快指针移动到结尾的时候，慢指针就移动到了待删除节点的前一个位置
	ListNode fast = newHead;
	ListNode slow = newHead;

	while(n > 0 && fast != null){
		fast = fast.next;
		n--;
	}

	while(fast != null && fast.next != null){
		fast = fast.next;
		slow = slow.next;
	}

	// 此时fast移动到了最后,slow在待删除节点的前一个位置，删除即可
	slow.next = slow.next.next;

	return newHead.next;
}

55-24. 两两交换链表中的节点【中等】【核心】

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

解法思路及注意点

理清思路才不会被指针搞来搞去，这里要注意的是如下：

两两交换，所以如果有奇数个节点的话，最后就会剩下一个节点，但是这个节点是不需要操作的

偶数的话，我们的目的就是两个两个交换，交换完一组之后我们需要前往下一组，但是在操作的过程中，头节点是在变动的，为了避免麻烦我们仍然可以用虚拟头节点dummy ，最后返回的是dummy.next即可

下面有一个重点操作cur = first ，这里理解了就能把握住整个操作，我们每一步都是两两交换，所以原来的第一个节点，也就是first，在交换之后就在这一组的最后一个，但同时也是下一组的first之前的节点，所以这样就能连接起来每一组的操作结果啦！！！

最终代码

java

public ListNode swapPairs(ListNode head) {
	// 创建一个虚拟头节点，指向真正的头节点
	ListNode dummy = new ListNode(-1, head);
	// cur 指向当前处理的前一个节点
	ListNode cur = dummy;

	// 循环条件：当前节点的下一个和下下个节点都存在
	while (cur.next != null && cur.next.next != null) {
		// 定义两个指针，分别指向要交换的两个节点，我们操作针对的就是这两个节点，其他都是辅助作用
		ListNode first = cur.next; // 第一个节点
		ListNode second = cur.next.next; // 第二个节点

		// 交换两个节点，我们的目标就是把原来 cur - first - second 变成 cur - second - first
		// 前一个节点指向第二个节点
		cur.next = second; 
		
		// 这一步本来我们只需要让second指向first就行了，但是为了下一次循环的指向，需要作如下
		// 第一个节点指向第二个节点的下一个节点
		first.next = second.next; 
		
		// 第二个节点指向第一个节点
		second.next = first; 

		// 移动 cur 到下一组的前一个节点
		cur = first;
	}
	// 返回真正的头节点
	return dummy.next;
}

56-25. K个一组反转链表【困难】【核心】

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

解法思路及注意点

全在注释里了，靠自己消化了

最终代码

java

public ListNode reverseKGroup(ListNode head, int k) {
	// 创建虚拟头节点，指向真正的头节点，方便统一处理
	ListNode dummy = new ListNode(-1, head);
	// pre 始终指向当前组的前一个节点（即上一组的尾节点）
	ListNode pre = dummy;

	while (true) {
		// 找到当前组的尾节点
		ListNode groupEnd = getGroupEnd(pre, k);
		if (groupEnd == null) {
			break; // 如果不足 k 个节点，结束
		}

		// 记录下一组的头节点，方便反转后连接
		ListNode nextGroupStart = groupEnd.next;
		// 断开当前组与下一组的连接，方便反转当前组
		// 如果不断开当前组与下一组的连接，反转时会把下一组的节点也一起反转
		groupEnd.next = null;
		// 记录当前组的头节点，反转后会变成当前组的尾节点
		ListNode groupStart = pre.next;
		// 反转当前组，并返回新的头节点
		ListNode newGroupHead = reverse(groupStart);
		// 将上一组的尾节点指向反转后的当前组头节点
		pre.next = newGroupHead;
		// 将反转后的当前组尾节点指向下一组的头节点
		groupStart.next = nextGroupStart;
		// 更新 pre 为当前组的尾节点，继续处理下一组
		pre = groupStart;
	}

	// 返回虚拟头节点的 next，即反转后的链表头节点
	return dummy.next;
} 

/**
 * 从 start 节点开始，找到第 k 个节点，即当前组的尾节点
 * 如果不足 k 个节点，返回 null
 */
private ListNode getGroupEnd(ListNode start, int k) {
	while (k > 0 && start != null) {
		start = start.next;
		k--;
	}
	return start;
}

/**
 * 反转链表，并返回新的头节点
 */
private ListNode reverse(ListNode head) {
	ListNode prev = null;
	ListNode curr = head;
	while (curr != null) {
		ListNode next = curr.next;
		curr.next = prev;
		prev = curr;
		curr = next;
	}
	return prev;
}

57-94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。

解法思路及注意点

递归和迭代法，中点是迭代，递归过于简单可能也会要求利用迭代的思路去写

这里主要是写一下迭代的思路：

迭代法替代递归法的思路在二叉树的遍历中，递归法是最直观的方式，因为它直接反映了遍历的顺序。然而，**递归法依赖于系统的调用栈，当树的高度较大时，可能会导致栈溢出 **。为了避免这个问题，我们可以使用迭代法来模拟递归的过程，利用显式的栈结构来替代系统的调用栈 。但是因为栈是FILO，所以要注意入栈的顺序问题，否则会模拟失败。下面第二段代码展示了递归思路
迭代法（中序遍历为例）迭代法的核心思想是使用栈来模拟递归的过程。具体步骤如下：
1. 初始化：创建一个空栈和一个空的结果列表。
2. 遍历左子树：从根节点开始，将当前节点及其所有左子节点依次压入栈中，直到左子节点为空。
3. 访问根节点：弹出栈顶节点，将其值加入结果列表。
4. 遍历右子树：将当前节点指向右子节点，重复步骤2和步骤3，直到栈为空且当前节点为空。

最终代码

（迭代法）

外层的 while 循环：控制整个遍历过程，直到栈为空且当前节点为空。
内层的 while 循环：将当前节点及其所有左子节点压入栈中，模拟递归遍历左子树的过程。
弹出栈顶节点：相当于递归法中访问根节点的操作。
转向右子树：模拟递归遍历右子树的过程。

java

public List<Integer> inorderTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<>();
	Deque<TreeNode> stack = new LinkedList<>();
	while (root != null || !stack.isEmpty()) {
		while (root != null) {
			// left root right
			stack.push(root);
			root = root.left;
		}
		// root
		root = stack.pop();
		res.add(root.val);
		// right
		root = root.right;
	}
	return res;
}

// 递归法
public List<Integer> inorderTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<Integer>();
	dfs(res, root);
	return res;
}

void dfs(List<Integer> res, TreeNode root) {
	if (root == null) {
		return;
	}
	// 按照 左-打印-右的方式遍历
	dfs(res, root.left);
	res.add(root.val);
	dfs(res, root.right);
}

这里因为这道题目太经典了，可以再写写前序和后序的代码

前序

java

public List<Integer> preorderTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<Integer>();
	dfs(res, root);
	return res;
}

void dfs(List<Integer> res, TreeNode root) {
	if (root == null) {
		return;
	}
	// 按照 打印-左-右的方式遍历
	res.add(root.val);
	dfs(res, root.left);
	dfs(res, root.right);
}

// 迭代
public List<Integer> preorderTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<>();
	Deque<TreeNode> stack = new LinkedList<>();
	if (root == null) {
		return res;
	}
	stack.push(root); // 先将根节点入栈
	while (!stack.isEmpty()) {
		TreeNode node = stack.pop(); // 弹出栈顶节点
		res.add(node.val); // 访问根节点
		// 先将右子节点入栈，再将左子节点入栈（保证左子节点先出栈）
		if (node.right != null) {
			stack.push(node.right);
		}
		if (node.left != null) {
			stack.push(node.left);
		}
	}
	return res;
}

后序

java

public List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<Integer>();
	dfs(res, root);
	return res;
}

void dfs(List<Integer> res, TreeNode root) {
	if (root == null) {
		return;
	}
	// 按照 左-右-打印的方式遍历
	dfs(res, root.left);
	dfs(res, root.right);
	res.add(root.val);
}

// 迭代
public List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<>();
	Deque<TreeNode> stack = new LinkedList<>();
	TreeNode prev = null; // 用于记录上一个访问的节点
	while (root != null || !stack.isEmpty()) {
		// 遍历左子树
		while (root != null) {
			stack.push(root);
			root = root.left;
		}
		// 弹出栈顶节点
		root = stack.pop();
		// 如果右子树为空或者右子树已经访问过，则访问当前节点
		if (root.right == null || root.right == prev) {
			res.add(root.val);
			prev = root; // 记录当前节点为已访问
			root = null; // 重置当前节点
		} else {
			// 否则，将当前节点重新入栈，并转向右子树
			stack.push(root);
			root = root.right;
		}
	}
	return res;
}

58-102. 二叉树的层序遍历【中等】

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

解法思路及注意点

层序遍历，其实就是为了之后的回溯做准备，使用的数据结构是Queue

最终代码

java

public List<List<Integer>> levelOrder(TreeNode root) {
	List<List<Integer>> res= new ArrayList<>();
	if(root == null){
		return res;
	}
	Queue<TreeNode> queue = new LinkedList<>(); // 使用队列进行层序遍历
	queue.offer(root);
	while(!queue.isEmpty()){
		// 记录当前层有几个节点，因为一直在进出，每次取值时都是队列中的剩余元素，恰好是当前层的节点数
		int curLevelLen = queue.size();
		List<Integer> line = new ArrayList<>();
		for(int i = 0; i < curLevelLen; i++){
			TreeNode node = queue.poll();
			line.add(node.val);
			if(node.left != null){
				queue.offer(node.left);
			}
			if(node.right != null){
				queue.offer(node.right);
			}
		}
		res.add(line);
	}
	return res;
}

59-104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

解法思路及注意点

二叉树的题目就是要理清遍历的方式

递归，左子树深度和右子树深度的最大值+自己本身（1）
其实是后序遍历
意图就是，从最底层逐层向上的反馈给父节点当前子节点的高度是多少
直到最后反馈给根节点，这时根节点的左右子树各自的高度就知道了,我们取其最大值+自身的高度1 即可

最终代码

java

public int maxDepth(TreeNode root) {
	return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

60-226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

解法思路及注意点

大多数对于二叉树的题目都是递归，直接理清思想就没问题

要翻转就是把自己左子树翻转然后把右子树翻转，最后把root的左右子树互换即可

是用递归的关键在于，要清楚返回值代表的是什么，不然很容易绕晕，最简单就是在最开始调用的一层理清返回值是什么，这样后面的也就清晰了

递归的核心在于：

分解问题：将大问题分解为更小的同类问题。
设计返回值：明确递归函数的返回值是什么，如何利用返回值。
确定终止条件：找到问题的最小规模，直接返回结果。
优化递归：通过备忘录或尾递归优化性能。

最终代码

java

public TreeNode invertTree(TreeNode root) {
	if (root == null) {
		return null;
	}
	// 递归的翻转左子树和右子树，让当前节点的left指向右子树，right指向左子树
	TreeNode r = invertTree(root.right);
	TreeNode l = invertTree(root.left);
	root.left = r;
	root.right = l;
	return root;
}

61-101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

解法思路及注意点

递归解决，核心就是按照对称的思路，【后序遍历】

对称二叉树是指一棵二叉树的左子树和右子树是镜像对称的。也就是说，从根节点开始，左子树的左节点和右子树的右节点相等，左子树的右节点和右子树的左节点相等，以此类推。它的核心思想是： 后序遍历，从底部逐层向上检查左右子树是否对称。

为什么是后序遍历？

后序遍历的顺序是 左-右-根，即先处理左子树，再处理右子树，最后处理根节点。在这道题中，递归函数的逻辑是：

左：检查左子树的左节点和右子树的右节点。
右：检查左子树的右节点和右子树的左节点。
根：将左右子树的结果取逻辑与。

最终代码

java

// 递归真是太牛逼啦！
// 其实是后序遍历,而且只能是后序遍历,因为我们要从底部逐层向上的告知顶部节点是否是对称的,直到到达根节点也是true
public boolean isSymmetric(TreeNode root) {
	if (root == null) {
		return false;
	}
	return isSymmetric(root.left, root.right);
}

public boolean isSymmetric(TreeNode l, TreeNode r) {
	if (l == null && r == null) {
		return true;
	}
	if (l == null || r == null) {
		return false;
	}
	if (l.val != r.val) {
		return false;
	}
	// 这里的return,其实就是后序遍历,
	// isSymmetric(l.left, r.right) 左
	// isSymmetric(l.right, r.left) 右
	// 两者取与运算 中
	return isSymmetric(l.left, r.right) && isSymmetric(l.right, r.left);
}

62-543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的长度由它们之间边数表示。

示例 1： 二叉树的直径

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

解法思路及注意点

二叉树的直径，关键是不要和高度、深度混淆，这里指的是“任意两个节点之间最长路径的长度”，所以应该是“**左右孩子的深度之和的最大值 **”

下面为什么要设计一个类主要是为了不想让结果值和方法本身耦合在一起

最终代码

java

public int diameterOfBinaryTree(TreeNode root) {
	// 使用一个独立的对象来存储最大直径
	DiameterResult result = new DiameterResult();
	depth(root, result);
	return result.getDiameter();
}

// 递归计算深度，同时更新最大直径
private int depth(TreeNode node, DiameterResult result) {
	if (node == null) {
		return 0; // 空树的深度为 0
	}
	// 递归计算左子树的深度
	int leftDepth = depth(node.left, result);
	// 递归计算右子树的深度
	int rightDepth = depth(node.right, result);
	// 更新最大直径
	result.updateDiameter(leftDepth + rightDepth);
	// 返回当前子树的深度
	return Math.max(leftDepth, rightDepth) + 1;
}

// 封装最大直径的类
class DiameterResult {
	private int diameter;

	public void updateDiameter(int newDiameter) {
		this.diameter = Math.max(this.diameter, newDiameter);
	}

	public int getDiameter() {
		return this.diameter;
	}
}

63-108. 将有序数组转化为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

解法思路及注意点

二分的思路，中间的节点是根节点，左边是左子树，右边是右子树，然后对左右子树分别递归

最终代码

java

public TreeNode sortedArrayToBST(int[] nums) {
	return process(nums, 0, nums.length - 1);
}

public TreeNode process(int[] nums, int l, int r) {
	if (l > r) {
		return null;
	}
	int mid = (l + r) >> 1;
	TreeNode root = new TreeNode(nums[mid]);
	root.left = process(nums, l, mid - 1);
	root.right = process(nums, mid + 1, r);
	return root;
}

64-98. 验证二叉搜索树【中等】

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下：

节点的左子树只包含** 小于 **当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解法思路及注意点

【核心】：对二叉搜索树进行【中序遍历】，结果是升序的，因此只要在中序遍历过程中发现当前值比前一个值还要小，那么就不符合。

在递归中维护一个全局状态，定义在外面才行，所以把pre这个指向前一个值的放在了外面

最终代码

java

// 如果满足二叉搜索树,则中序遍历的结果就是升序的
private long prev = Long.MIN_VALUE;

public boolean isValidBST(TreeNode root) {
	if (root == null) {
		return true;
	}
	if (!isValidBST(root.left)) {
		return false;
	}
	// 不满足二叉搜索树条件
	// prev其实就是左节点,左节点比当前节点还要小,那肯定不是二叉搜索树
	if (root.val <= prev) {
		return false;
	}
	prev = root.val;
	return isValidBST(root.right);
}

65-230. 二叉搜索树中第k小的数【中等】

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k小的元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

解法思路及注意点

如果看了上一题“验证二叉搜索树”你就会发现极其简单，因为我们只需要对二叉搜索树做一个中序遍历，得到的结果就是升序的，所以第k小的数，其实就是我们从开始遍历到第i个值的结果

我们可以不需要传统的中序遍历，把所有值加入到结果集中，然后从结果集中取到第k个值，而是直接“数到”第k个值

最终代码

java

private int count = 0;
private int result = 0;

public int kthSmallest(TreeNode root, int k) {
	count = k;
	inorder(root);
	return result;
}

private void inorder(TreeNode root) {
	if (root == null) {
		return;
	}
	inorder(root.left); // 遍历左子树
	count--;
	if (count == 0) {
		result = root.val; // 找到第 k 小的元素
		return;
	}
	inorder(root.right); // 遍历右子树
}

66-199. 二叉树的右视图【中等】

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1： **输入：**root = [1,2,3,null,5,null,4] 输出：[1,3,4] 解释： 二叉树的右视图

解法思路及注意点

用到层序遍历的思想，直接模拟即可，但是不要简单的以为只要放最右边的值就可以了，还是需要放入左边的node兜底的，因为你只放右节点，无法保证所有层的节点都被遍历到

最终代码

java

public List<Integer> rightSideView(TreeNode root) {
	// 层序遍历的思想，但是我不需要把每一层所有节点都放进去，只需要放最右侧的节点即可
	List<Integer> res = new ArrayList<>();
	if (root == null) {
		return res;
	}
	Queue<TreeNode> queue = new LinkedList<>(); // 使用队列进行层序遍历
	queue.offer(root);
	while (!queue.isEmpty()) {
		// 记录当前层有几个节点，因为一直在进出，每次取值时都是队列中的剩余元素，恰好是当前层的节点数
		int curLevelLen = queue.size();
		TreeNode node = new TreeNode();
		for (int i = 0; i < curLevelLen; i++) {
			node = queue.poll();

			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
		}
		// for结束时的node指向的就是该层最后一个节点
		res.add(node.val);
	}
	return res;
}

67-114. 二叉树展开为链表【中等】

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 **先序遍历 ** 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

解法思路及注意点

这里要看清题目要求，最后的链表有要求的，左为null，右为下一个节点，要求前序遍历

典中典❌：可以直接前序遍历然后保存到list，接着按顺序遍历list构造最新的链表
牛种牛🐂：可以在边前序遍历的时候边修改节点，但是容易写错，慎用，理解清楚后使用

最终代码

java

List<TreeNode> preOrderNodeList = new ArrayList<>();

public void flatten(TreeNode root) {
	if (root == null) {
		return;
	}
	preOrder(root);
	int size = preOrderNodeList.size();
	TreeNode newRoot = preOrderNodeList.get(0);

	for (int i = 1; i < size; i++) {
		TreeNode cur = preOrderNodeList.get(i);
		newRoot.left = null;
		newRoot.right = cur;
		newRoot = cur;
	}
}

public void preOrder(TreeNode root) {
	if (root == null) {
		return;
	}
	// 先先序遍历
	preOrderNodeList.add(root);
	preOrder(root.left);
	preOrder(root.right);
}


// 另一种

private TreeNode prev = null;

public void flatten(TreeNode root) {
	if (root == null) {
		return;
	}
	// 将当前节点的 right 指针指向下一个节点，left 指针置为 null
	if (prev != null) {
		prev.left = null;
		prev.right = root;
	}
	prev = root; // 更新 prev
	// 注意：先保存右子节点，因为展开过程会修改指针
	TreeNode right = root.right;
	flatten(root.left); // 遍历左子树
	flatten(right); // 遍历右子树
}

68-105. 从前序遍历和中序遍历序列构造二叉树【中等】

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历 ，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

解法思路及注意点

【核心】：前序遍历即根左右，中序遍历即左根右；前序遍历数组的首个元素一定是整棵树的根节点，那在中序遍历数组中找到这个点，以这个点为分割点，前面是左子树（记长度为leftLen），右面就是右子树（记长度为rightLen），同时也可以对应在前序遍历的数组上，此时，在第二个元素开始到leftLen就是左子树的区间，后面就是右子树的区间，再递归完成逻辑即可

最终代码

java

// 因为题目保证了每个元素都不会重复
Map<Integer, Integer> index = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
	// 为了查找下标方便,把中序数组索引先放在map里
	for (int i = 0; i < inorder.length; i++) {
		index.put(inorder[i], i);
	}
	// 做题关键在于区间的边界加不加入运算，从这里传入的值我们可以直到是左闭右开区间
	return construct(preorder, 0, preorder.length, inorder, 0, inorder.length);
}

// 返回构造好的子树的根节点
public TreeNode construct(int[] preorder, int preStart, int preEnd,
		int[] inorder, int inStart, int inEnd) {
	if (preStart >= preEnd || inStart >= inEnd) {
		// 说明不满足左闭右开区间
		return null;
	}
	// 找到前序数组的第一个元素在中序遍历中的位置(即根节点)
	int rootIndex = index.get(preorder[preStart]);
	TreeNode root = new TreeNode(inorder[rootIndex]);
	// 根据找到的根节点,中序数组分成了左中序和右中序两段,分别代表左子树和右子树
	// 保存中序左子树个数，用来确定后序数列的个数
	int lenOfLeft = rootIndex - inStart;
	root.left = construct(preorder, preStart + 1, preStart + 1 + lenOfLeft,
			inorder, inStart, rootIndex);
	root.right = construct(preorder, preStart + lenOfLeft + 1, preEnd,
			inorder, rootIndex + 1, inEnd);
	return root;
}

69-200. 岛屿数量【中等】

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

解法思路及注意点

这道题目主要是搜索矩阵里面“连通性”的1，属于连通性问题，我们需要一个“传染算法”，即找到符合要求的一个点时，根据题目要求的向四周扩散地“传染”，即把这个找到的符合要求的点，向四周扩展，把与它连通性的所有点一起都标记为已经处理过的节点，这样下一次循环进来的时候再找到下一个符合条件的点，这个点就是和刚刚那个点没有“连通性”的点

最终代码

java

public int numIslands(char[][] grid) {
	int count = 0;
	int m = grid.length;
	int n = grid[0].length;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] == '1') {
				infect(grid, i, j);
				count++;
			}
		}
	}
	return count;
}

public void infect(char[][] grid, int i, int j) {
	int m = grid.length;
	int n = grid[0].length;
	if (grid[i][j] == '1') {
		// 将‘1’变成‘.’表示已经计算过
		grid[i][j] = '.';
		if (i - 1 >= 0 && grid[i - 1][j] == '1') {
			infect(grid, i - 1, j);
		}
		if (i + 1 < m && grid[i + 1][j] == '1') {
			infect(grid, i + 1, j);
		}
		if (j - 1 >= 0 && grid[i][j - 1] == '1') {
			infect(grid, i, j - 1);
		}
		if (j + 1 < n && grid[i][j + 1] == '1') {
			infect(grid, i, j + 1);
		}
	}
}

70-994. 腐烂的橘子【中等】

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

解法思路及注意点

和上一题岛屿问题，都属于连通性问题，别看代码多，实际上很简单

最终代码

java

public int orangesRotting(int[][] grid) {
	int m = grid.length;
	int n = grid[0].length;
	int step = 0;
	int count = count(grid);
	int lastCount = -1;
	// 只要还有新鲜的橘子就循环
	while (count > 0) {
		// 如果相邻的两次新鲜橘子个数没变，说明永远不能再传染了，停止即可
		if (lastCount == count) {
			return -1;
		}
		step++;
		for (int y = 0; y < m; y++) {
			for (int x = 0; x < n; x++) {
				if (grid[y][x] == 2) {
					infect(grid, x, y);
				}
			}
		}
		// 一次感染已经结束，更新变量即可
		lastCount = count;
		count -= flash(grid);
	}
	// 还有新鲜橘子存在
	return step;
}

/*
 * 刷新算法
 * 返回此次传染成功传染的个数
 * 并将他们由-2更新为2
 */
public int flash(int[][] grid) {
	int m = grid.length;
	int n = grid[0].length;
	int count = 0;
	for (int y = 0; y < m; y++) {
		for (int x = 0; x < n; x++) {
			if (grid[y][x] == -2) {
				grid[y][x] = 2;
				count++;
			}
		}
	}
	return count;
}

/*
 * 传染算法
 * 真正的传染
 */
public void infect(int[][] grid, int x, int y) {
	int m = grid.length;
	int n = grid[0].length;
	if (x < 0 || x >= n) {
		return;
	}
	if (y < 0 || y >= m) {
		return;
	}
	// 如果当前位置是一个腐烂的句子，就试着传染四周
	if (grid[y][x] == 2) {
		mark(grid, x + 1, y);
		mark(grid, x - 1, y);
		mark(grid, x, y + 1);
		mark(grid, x, y - 1);
	}
}

/*
 * 标记算法，将新鲜橘子标记为腐烂橘子(标记为-2）
 * 以便于区分原有的腐烂句子，区分的意义实现以后就可以再标记为2，和其他腐烂橘子一样了
 */
public void mark(int[][] grid, int x, int y) {
	int m = grid.length;
	int n = grid[0].length;
	if (x < 0 || x >= n) {
		return;
	}
	if (y < 0 || y >= m) {
		return;
	}
	if (grid[y][x] == 1) {
		grid[y][x] = -2;
	}
}

/*
 * 记录当前情况下新鲜橘子的总数
 */
public int count(int[][] grid) {
	int m = grid.length;
	int n = grid[0].length;
	int count = 0;
	for (int y = 0; y < m; y++) {
		for (int x = 0; x < n; x++) {
			if (grid[y][x] == 1) {
				count++;
			}
		}
	}
	return count;
}

71-46. 全排列【中等】

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

解法思路及注意点

回溯经典，但是要注意代码中添加结果的地方

在代码中，res.add(new ArrayList<>(line)); 的作用是将当前 line 的内容复制到一个新的 ArrayList 中，并将这个新的 ArrayList 添加到 res 中。这种方式确保了 res 中的每个元素都是独立的列表，而不是对同一个 line 对象的引用。

为什么不能直接使用res.add(line)？

如果直接使用 res.add(line)，res 中存储的将是 line 对象的引用，而不是 line 的内容。这意味着，当 line 在后续的回溯过程中被修改时， res 中已经存储的 line 也会随之改变，因为它们引用的是同一个对象。最终，res 中的所有元素都会是相同的，即 line 的最终状态。

为什么需要使用new ArrayList<>(line)？

通过使用 new ArrayList<>(line)，我们创建了一个新的 ArrayList 对象，并将 line 的内容复制到这个新对象中。这样，即使 line 在后续的回溯过程中被修改，res 中已经存储的列表也不会受到影响，因为它们是完全独立的对象。

示例说明

假设 nums = [1, 2, 3]，在回溯过程中，line 会经历以下状态：

line = [1]
line = [1, 2]
line = [1, 2, 3] （此时 line.size() == nums.length，将其添加到 res）
line = [1, 2] （回溯，移除最后一个元素）
line = [1, 3]
line = [1, 3, 2] （再次添加到 res）

如果直接使用 res.add(line)，res 中的两个列表都会是 [1, 3, 2]，因为它们都引用同一个 line 对象。而使用 res.add(new ArrayList<>(line))，res 中的两个列表分别是 [1, 2, 3] 和 [1, 3, 2]，它们是独立的列表。

最终代码

java

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> line = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        // 将每个位置的使用情况记录下来,默认是false
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        backtracking(nums, used);
        return res;
    }

    private void backtracking(int[] nums, boolean[] used) {
        // 当line里面收集的数量达到nums.length就是收集结果的时候
        if (line.size() == nums.length) {
            res.add(new ArrayList<>(line));
            return;
        }
        for (int i = 0; i < used.length; i++) {
            if (!used[i]) {
                line.add(nums[i]);
                used[i] = true;
                backtracking(nums, used);
                line.remove(line.size() - 1);
                used[i] = false;
            }
        }
    }
}

72-78. 子集【中等】

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

解法思路及注意点

子集问题的特点：在递归的每一层都需要记录结果，而不是仅仅在叶子节点记录。
回溯的核心：通过递归和回溯，枚举所有可能的子集。
去重：通过 startIndex 控制遍历的起始位置，避免重复选择元素。
结果记录：每次进入递归时，line 的当前状态就是一个子集，需要记录下来。

最终代码

java

/**
 * 回溯算法
 * 子集这道题强调的是,树形结构中,每一层上节点都是我们想要的结果
 * 前面的题目是,叶子节点才是收获节点的时候
 * 所以做回溯题还是要先画好树形结构
 */
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> line = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
        process(nums, 0);
        return res;
    }

    private void process(int[] nums, int startIndex) {
        // 从最上面说的,每进入一次递归,都是一次收获结果的时候
        res.add(new ArrayList<>(line));
        if (startIndex >= nums.length) {
            // 说明所有数字都选过了
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            line.add(nums[i]);
            process(nums, i + 1);
            line.remove(line.size() - 1);
        }
    }
}

73-17. 电话号码的数字组合【中等】

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

最终代码

java

class Solution {
    // 数字键与拼音的对应集
    final String[] m = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> res = new ArrayList<>();
    // 存储中间结果
    StringBuilder line = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return new ArrayList<>();
        }
        process(digits, 0);
        return res;
    }

    /**
     * @param digits 数字串
     * @param index  处理到哪一个数字
     */
    private void process(String digits, int index) {
        if (index == digits.length()) {
            // 表示当前已经处理完了所以数字组合
            res.add(line.toString());
            return;
        }
        // 当前index处表示的数字
        int digitsIndex = digits.charAt(index) - '0';
        char[] letter = m[digitsIndex].toCharArray();
        for (int i = 0; i < letter.length; i++) {
            line.append(letter[i]);
            process(digits, index + 1);
            line.deleteCharAt(line.length() - 1);
        }
    }
}

74-39. 组合总和【中等】

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

解法思路及注意点

题目关键在于“同一个数字可以被无限制使用”，和为target还要借鉴排序的思路，做剪枝处理，去掉无意义的递归

最终代码

java

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        // 先进行排序
        Arrays.sort(candidates);
		
        backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

    public void backtracking(List<List<Integer>> res, List<Integer> path, 
			int[] candidates, int target, int sum, int idx) {
        
		// 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(res, path, candidates, target, sum + candidates[i], i);
            // 回溯，移除路径 path 最后一个元素
            path.remove(path.size() - 1);
        }
    }
}

75-22. 括号生成【中等】

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 **有效的 **括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

解法思路及注意点

遵循括号匹配的原则做回溯

最终代码

java

class Solution {

    List<String> res = new ArrayList<>();

    /**
     * 根据括号的匹配原则,当左右数量相同时,只能添加左括号
     * 当左括号小于n时,可以添加左括号
     * 当右括号小于n时,可以添加右括号
     * 左右括号的数量都必须得小于n
     */
    public List<String> generateParenthesis(int n) {
        char[] line = new char[n * 2];
        process(line, 0, 0, 0, n);
        return res;
    }

    public void process(char[] line, int index, int leftCount, int rightCount, int n){
        if (index == n * 2) {
            // 说明左右括号的数量已经达到了n对
            res.add(new String(line));
            return;
        }
        if (leftCount == rightCount) {
            // 如果左右括号数相等,则此时只能加入左括号
            line[index] = '(';
            process(line, index + 1, leftCount + 1, rightCount, n);
            return;
        }
        if (leftCount < n) {
            line[index] = '(';
            process(line, index + 1, leftCount + 1, rightCount, n);
        }
        if (rightCount < n) {
            line[index] = ')';
            process(line, index + 1, leftCount, rightCount + 1, n);
        }
    }
}

76-79. 单词搜索【中等】

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

解法思路及注意点

开始进行递归的地方可以选择，只有第一个字符匹配的位置才开始递归，递归中维护一个index值表示当前已经匹配了index-1个字符正在寻找第index个字符，因此递归结束条件是index指向word的长度时停止

最终代码

java

class Solution {
    /**
     * 遍历整个数组, 每次都以当前位置出发,想四周扩散的去找,知道找到了满足条件的时候就返回true
     */
    public boolean exist(char[][] board, String word) {
        char[] wordChar = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 对于每一个元素都要试一下process,从word的起点开始扫描(index初始为0)
                final boolean process = process(board, wordChar, i, j, 0);
                if(process){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 检查当前是否已经存在单词
     * @param board 元数据
     * @param word 单词
     * @param i 元数据横坐标
     * @param j 元数据纵坐标
     * @param index 当前单词位置
     * @return 是否已经存在单词
     */
    public boolean process(char[][] board, char[] word, int i, int j, int index){
        if (index == word.length) {
            // 当前已经找到了word
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            // 非法下标
            return false;
        }
        if (board[i][j] == word[index]) {
            board[i][j] = (char)(-board[i][j]);
            // 说明当前遍历到的是index处的字符,即可上下左右的去寻找"没有用过的且匹配的字符"
            boolean p1 = process(board, word, i - 1, j, index + 1);
            boolean p2 = process(board, word, i + 1, j, index + 1);
            boolean p3 = process(board, word, i, j - 1, index + 1);
            boolean p4 = process(board, word, i, j + 1, index + 1);
            // 回溯
            board[i][j] = (char)(-board[i][j]);
            return p1 || p2 || p3 || p4;
        }else{
            return false;
        }
    }
}

77-131. 分割回文串【中等】

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

解法思路及注意点

这个题就是给出子集的条件下，让子集满足是回文结构，所以关键是子集

最终代码

java

class Solution {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> partition(String s) {
        process(s.toCharArray(), 0, new ArrayList<>());
        return res;
    }

    public void process(char[] chars, int index, List<String> line) {
        if (index == chars.length) {
            res.add(new ArrayList<>(line));
            return;
        }
        for (int i = index; i < chars.length; i++) {
            if (isPalindrome(chars, index, i)) {
                line.add(new String(Arrays.copyOfRange(chars, index, i + 1)));
                process(chars, i + 1, line);
                // 因为是ArrayList有序的,回溯
                line.remove(line.size() - 1);
            }
        }
    }

    // 判断是否回文结构
    private boolean isPalindrome(char[] chars, int l, int r) {
        if (l == r) {
            return true;
        }
        while (l < r) {
            if (chars[l] != chars[r]) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

78-51. N皇后【困难】

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

解法思路及注意点

N皇后其实思路挺简单，但是代码实现确实是硬伤，没啥好说的，多练吧！

最终代码

java

class Solution {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(n, 0, chessboard);
        return res;
    }


    public void backTrack(int n, int row, char[][] chessboard) {
        if (row == n) {
            List<String> collect = Arrays.stream(chessboard)
                    .map(chars -> String.copyValueOf(chars))
                    .collect(Collectors.toList());
            res.add(collect);
            return;
        }

        for (int col = 0; col < n; ++col) {
            if (isValid(row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                backTrack(n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }

    }

    public boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i = 0; i < row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        // 检查45度对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

79-35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

解法思路及注意点

二分法经典

最终代码

java

public int searchInsert(int[] nums, int target) {
	// 二分搜索 秒了
	int l = 0;
	int r = nums.length - 1;
	int m = 0;
	while (l <= r) {
		m = l + ((r - l) >> 1);
		if (target == nums[m]) {
			return m;
		} else if (target > nums[m]) {
			l = m + 1;
		} else if (target < nums[m]) {
			r = m - 1;
		}
	}
	return l;
}

80-74. 搜索二位矩阵【中等】

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

解法思路及注意点

本质是两次二分查找

最终代码

java

// 两次二分查找
public boolean searchMatrix(int[][] matrix, int target) {
	int l = 0;
	int r = matrix.length - 1;
	int res = -1;
	while (l <= r) {
		int m = l + ((r - l) >> 1);
		if (matrix[m][0] <= target) {
			res = m;
			l = m + 1;
		} else if (matrix[m][0] > target) {
			r = m - 1;
		}
	}
	if(res < 0){
		return false;
	}
	// 此时res就是找到的那一行，答案就在这一行当中，否则就不存在
	l = 0;
	r = matrix[0].length - 1;
	while (l <= r) {
		int m = l + ((r - l) >> 1);
		if (matrix[res][m] == target) {
			return true;
		} else if (matrix[res][m] > target) {
			r = m - 1;
		} else if (matrix[res][m] < target) {
			l = m + 1;
		}
	}
	return false;
}

41-53. 最大子数组和【中等】 ​

解法思路及注意点 ​

最终代码 ​

42-56. 合并区间【中等】 ​

解法思路及注意点 ​

最终代码 ​

43-73. 矩阵置零【中等】 ​

解法思路及注意点 ​

最终代码 ​

44-54. 螺旋矩阵【中等】 ​

解法思路及注意点 ​

最终代码 ​

45-48. 旋转图像【中等】 ​

解法思路及注意点 ​

最终代码 ​

46-240. 搜索二位矩阵II【中等】 ​

解法思路及注意点 ​

最终代码 ​

47-160. 相交链表 ​

解法思路及注意点 ​

最终代码 ​

48-206. 反转链表【核心】 ​

解法思路及注意点 ​

最终代码 ​

49-234. 回文链表 ​

解法思路及注意点 ​

最终代码 ​

50-141. 环形链表 ​

解法思路及注意点 ​

最终代码 ​

51-142. 环形链表II【中等】 ​

解法思路及注意点 ​

最终代码 ​

52-21. 合并两个有序链表 ​

解法思路及注意点 ​

最终代码 ​

53-2. 两数相加【中等】 ​

解法思路及注意点 ​

最终代码 ​

54-19. 删除链表的倒数第N个节点【中等】 ​

解法思路及注意点 ​

最终代码 ​

55-24. 两两交换链表中的节点【中等】【核心】 ​

解法思路及注意点 ​

最终代码 ​

56-25. K个一组反转链表【困难】【核心】 ​

解法思路及注意点 ​

最终代码 ​

57-94. 二叉树的中序遍历 ​

解法思路及注意点 ​

最终代码 ​

58-102. 二叉树的层序遍历【中等】 ​

解法思路及注意点 ​

最终代码 ​

59-104. 二叉树的最大深度 ​

解法思路及注意点 ​

最终代码 ​

60-226. 翻转二叉树 ​

解法思路及注意点 ​

最终代码 ​

61-101. 对称二叉树 ​

解法思路及注意点 ​

为什么是后序遍历？ ​

最终代码 ​

62-543. 二叉树的直径 ​

解法思路及注意点 ​

最终代码 ​

63-108. 将有序数组转化为二叉搜索树 ​

解法思路及注意点 ​

最终代码 ​

64-98. 验证二叉搜索树【中等】 ​

解法思路及注意点 ​

最终代码 ​

65-230. 二叉搜索树中第k小的数【中等】 ​

解法思路及注意点 ​

最终代码 ​

66-199. 二叉树的右视图【中等】 ​

解法思路及注意点 ​

最终代码 ​

67-114. 二叉树展开为链表【中等】 ​

41-53. 最大子数组和【中等】

解法思路及注意点

最终代码

42-56. 合并区间【中等】

解法思路及注意点

最终代码

43-73. 矩阵置零【中等】

解法思路及注意点

最终代码

44-54. 螺旋矩阵【中等】

解法思路及注意点

最终代码

45-48. 旋转图像【中等】

解法思路及注意点

最终代码

46-240. 搜索二位矩阵II【中等】

解法思路及注意点

最终代码

47-160. 相交链表

解法思路及注意点

最终代码

48-206. 反转链表【核心】

解法思路及注意点

最终代码

49-234. 回文链表

解法思路及注意点

最终代码

50-141. 环形链表

解法思路及注意点

最终代码

51-142. 环形链表II【中等】

解法思路及注意点

最终代码

52-21. 合并两个有序链表

解法思路及注意点

最终代码

53-2. 两数相加【中等】

解法思路及注意点

最终代码

54-19. 删除链表的倒数第N个节点【中等】

解法思路及注意点

最终代码

55-24. 两两交换链表中的节点【中等】【核心】

解法思路及注意点

最终代码

56-25. K个一组反转链表【困难】【核心】

解法思路及注意点

最终代码

57-94. 二叉树的中序遍历

解法思路及注意点

最终代码

58-102. 二叉树的层序遍历【中等】

解法思路及注意点

最终代码

59-104. 二叉树的最大深度

解法思路及注意点

最终代码

60-226. 翻转二叉树

解法思路及注意点

最终代码

61-101. 对称二叉树

解法思路及注意点

为什么是后序遍历？

最终代码

62-543. 二叉树的直径

解法思路及注意点

最终代码

63-108. 将有序数组转化为二叉搜索树

解法思路及注意点

最终代码

64-98. 验证二叉搜索树【中等】

解法思路及注意点

最终代码

65-230. 二叉搜索树中第k小的数【中等】

解法思路及注意点

最终代码

66-199. 二叉树的右视图【中等】

解法思路及注意点

最终代码

67-114. 二叉树展开为链表【中等】