# leetcode_work **Repository Path**: italonger/leetcode_work ## Basic Information - **Project Name**: leetcode_work - **Description**: 记录一些日常刷题笔记 - **Primary Language**: Java - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2023-08-14 - **Last Updated**: 2024-04-20 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README --- title: 专题突击算法 --- ## 1.二分查找 ### 二分查找-牛客 #### 描述 请实现有重复数字的升序数组的二分查找。 输出在数组中第一个大于等于查找值的位置（下标从1开始算起），如果数组中不存在这样的数(指不存在大于等于查找值的数)，则输出数组长度加一。 #### 示例1 输入： ``` 5,4,[1,2,4,4,5] ``` 复制 返回值： ``` 3 ``` 复制 说明： ``` 输出位置从1开始计算 ``` #### 示例2 输入： ``` 5,4,[1,2,3,3,5] ``` 复制 返回值： ``` 5 ``` 复制 说明： ``` 虽然数组中没有4，但 5 ≥ 4 ，所以返回5对应的位置，刚好也是5。 ``` #### 分析 这个二分就很好理解了，首先，将v减1，是为了将查找目标从1开始计数转换为从0开始计数。然后，使用二分查找算法在数组a中查找第一个大于等于v的元素。初始化左右指针left和right分别指向数组的第一个元素和最后一个元素。在每一次循环中，计算中间元素的下标mid，如果v大于等于a[mid]，则更新left为mid；否则，更新right为mid。直到left大于right，查找结束。最后，判断left的值是否小于等于n-1，如果是，则返回left+1，即为第一个大于v的元素的下标；否则，返回n+1，表示数组中不存在大于v的元素。 ```java public int upper_bound_ (int n, int v, int[] a) { v = v - 1; //从0开始 int left = 0,right = n - 1; while (left <= right){ int mid = (left + right) / 2; if (v >= a[mid]){ left = mid; }else { right = mid; } } //最后返回下标.. if (left <= n-1){ return left + 1; }else { return n+1; } } ``` ### 求X的平方根+1 #### 描述 给你一个非负整数 `x` ，计算并返回 `x` 的 **算术平方根** 。 由于返回类型是整数，结果只保留 **整数部分** ，小数部分将被 **舍去 。** **注意：**不允许使用任何内置指数函数和算符，例如 `pow(x, 0.5)` 或者 `x ** 0.5` 。 **示例 1：** ``` 输入：x = 4 输出：2 ``` **示例 2：** ``` 输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。 ``` **提示：** - `0 <= x <= 231 - 1` #### 分析 直接二分，主要是确定好一点，就是它无限趋向最大值时，可能会导致x*x的最大值超过int，所以需要转为浮点型，同时也方便计算： ```Java public int mySqrt(int x) { int l =0,r=x,ans=-1; while (l<=r){ int mid = l+(r-l)/2; if ((long)mid * mid <=x){ ans = mid; l=mid+1; }else{ r=mid-1; } } return ans; } ``` 看到一种当时笨猪的我没想到的简单粗暴的哈哈： ```Java public int mySqrt(int x) { long mid = 0; for(long i = 0; i * i <= x;i++){ mid = i; } return (int)mid; } ``` ## 滑动窗口 ### 滑动窗口的最大值 #### 描述 给定一个数组 `nums` 和滑动窗口的大小 `k`，请找出所有滑动窗口里的最大值。 #### **示例1:** ``` 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 ``` #### 难度 困难 #### 分析 最开始我想的暴力破解，首先，代码会检查k是否等于1，如果是的话，直接返回原数组nums。接下来，定义一个长度为nums.length-k+1的数组arr，用于存储最后输出的结果。然后，通过一个循环遍历数组nums，i从0开始，j从0开始，循环条件是i小于nums.length-k+1。在循环中，通过另一个循环来找到每个大小为k的连续子数组的最大值。内部循环的条件是j小于k。在内部循环中，首先判断arr[i]是否小于nums[i+j]，如果是的话，将nums[i+j]赋值给arr[i]，即更新arr[i]为当前最大值。然后，j加1，继续下一轮内部循环。当内部循环结束后，将j重置为0，再进行下一轮外部循环。最后，返回数组arr作为结果。就有了以下代码： ```Java public static int[] maxSlidingWindow(int[] nums, int k) { if (k == 1)return nums; int[] arr = new int[nums.length-k+1];//存最后输出的 for (int i = 0,j=0; i < nums.length-k+1; i++) { arr[i] = nums[i]; while(j < k){ if(nums[i+j] > 0 && arr[i] < nums[i+j]){ arr[i] = nums[i+j]; } j++; } j = 0; } return arr; } ``` 不过很遗憾，这种方式样例没全部通过，时间也超过了...（2万多值的窗口只能说换思路...） 下面这种思路： ```Java public int[] maxSlidingWindow(int[] nums, int k) { if(nums.length == 0 || k == 0) return new int[0]; Deque deque = new LinkedList<>(); int[] res = new int[nums.length - k + 1]; for(int j = 0, i = 1 - k; j < nums.length; i++, j++) { // 删除 deque 中对应的 nums[i-1] if(i > 0 && deque.peekFirst() == nums[i - 1]) deque.removeFirst(); // 保持 deque 递减 while(!deque.isEmpty() && deque.peekLast() < nums[j]) deque.removeLast(); deque.addLast(nums[j]); // 记录窗口最大值 if(i >= 0) res[i] = deque.peekFirst(); } return res; } ``` ## 2.数组 ### 合并两个有序数组+2 #### 描述 给你两个按 **非递减顺序** 排列的整数数组 `nums1` 和 `nums2`，另有两个整数 `m` 和 `n` ，分别表示 `nums1` 和 `nums2` 中的元素数目。 请你 **合并** `nums2` 到 `nums1` 中，使合并后的数组同样按 **非递减顺序** 排列。 **注意：**最终，合并后数组不应由函数返回，而是存储在数组 `nums1` 中。为了应对这种情况，`nums1` 的初始长度为 `m + n`，其中前 `m` 个元素表示应合并的元素，后 `n` 个元素为 `0` ，应忽略。`nums2` 的长度为 `n` 。 **示例 1：** ``` 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。 ``` **示例 2：** ``` 输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。 ``` **示例 3：** ``` 输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。 ``` **提示：** - `nums1.length == m + n` - `nums2.length == n` - `0 <= m, n <= 200` - `1 <= m + n <= 200` - `-109 <= nums1[i], nums2[j] <= 109` #### 分析 我们可以从题目中很明确的看到，我需要的就是比较，但是怎么比较比较高效呢？我们直接比两个数组的最大值，依次递减，直到p2的为0，哪怕p1还有也已经满足条件了因为我们是放入p1： ```Java class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { //给定三个指针 int p1=m-1,p2=n-1,p3=m+n-1; while(p2>=0){ if (p1>=0 && nums1[p1]>nums2[p2]){//需要让nums1里面的也排序 nums1[p3--]=nums1[p1--]; }else{ nums1[p3--]=nums2[p2--]; } } } } ``` ### 库存管理II+2 #### 描述 仓库管理员以数组 `stock` 形式记录商品库存表。`stock[i]` 表示商品 `id`，可能存在重复。请返回库存表中数量大于 `stock.length / 2` 的商品 `id`。 #### **示例 1:** ``` 输入: stock = [6, 1, 3, 1, 1, 1] 输出: 1 ``` **限制：** - `1 <= stock.length <= 50000` - 给定数组为非空数组，且存在结果数字 #### 难度 容易 #### 描述 常规三种办法：1.使用map来统计数字数量出现最多的就是众数；2.摩尔计数法，假设当前数是众数，是这个数就+1，不是就-1，遍历完返回x即可；3.排序数组，中间的数一定是众数： ```Java class Solution { public int inventoryManagement(int[] stock) { int x =0,votes=0; for(int num:stock){ if(votes == 0){ x = num; } votes += num == x ? 1:-1; } return x; } } ``` ### 岛屿最大面积+2 #### 描述 给你一个大小为 `m x n` 的二进制矩阵 `grid` 。 **岛屿** 是由一些相邻的 `1` (代表土地) 构成的组合，这里的「相邻」要求两个 `1` 必须在 **水平或者竖直的四个方向上** 相邻。你可以假设 `grid` 的四个边缘都被 `0`（代表水）包围着。 岛屿的面积是岛上值为 `1` 的单元格的数目。 计算并返回 `grid` 中最大的岛屿面积。如果没有岛屿，则返回面积为 `0` 。 #### **示例 1：** ![img](https://assets.leetcode.com/uploads/2021/05/01/maxarea1-grid.jpg) ``` 输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] 输出：6 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。 ``` #### **示例 2：** ``` 输入：grid = [[0,0,0,0,0,0,0,0]] 输出：0 ``` **提示：** - `m == grid.length` - `n == grid[i].length` - `1 <= m, n <= 50` - `grid[i][j]` 为 `0` 或 `1` #### 分析 dfs直接简单粗暴，我们先确定好边界，上下左右边界，看提示，之后需要把遍历过的变成海洋，赋值为1然后递归就行了 ```Java public int maxAreaOfIsland(int[][] grid) { int max = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid.length; j++) { if (grid[i][j]==1){ max = Math.max(max,dfs(grid,i,j)); } } } return max; } private int dfs(int[][] grid, int i, int j) { if (i < 0 || j <0 || i>=grid.length || j >=grid.length || grid[i][j]==0){ return 1; } grid[i][j]=0; int sum = 1; //向上遍历 sum+=dfs(grid,i-1,j); sum+=dfs(grid,i+1,j); sum+=dfs(grid,i,j+1); sum+=dfs(grid,i,j-1); return sum; } ``` 之后做了一道求周长的，也可以用dfs做，但是有点不同，这个周长需要的是累加，在max上累加而不是最大，同时，它只要在边界或者超过长度，又或者遇到海洋就要+1，之后递归相加即可： ```Java public int islandPerimeter(int[][] grid) { int max = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[i].length; j++) { if (grid[i][j]==1){ max += dfs(grid,i,j); } } } return max; } private int dfs(int[][] grid, int i, int j) { if (i<0||j<0||i>=grid.length||j>=grid[i].length){ return 1; } if (grid[i][j]==2){ return 0; } if (grid[i][j]==0){ return 1; } grid[i][j]=2; return dfs(grid,i+1,j)+ dfs(grid,i-1,j)+ dfs(grid,i,j+1)+ dfs(grid,i,j-1); } ``` ### 接雨水-x #### 描述 给定 `n` 个非负整数表示每个宽度为 `1` 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 #### **示例 1：** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/rainwatertrap.png) ``` 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 ``` #### **示例 2：** ``` 输入：height = [4,2,0,3,2,5] 输出：9 ``` **提示：** - `n == height.length` - `1 <= n <= 2 * 104` - `0 <= height[i] <= 105` #### 分析 动态规划分析好各种情况就行，我们只需要知道，该点左边的高度和右边的高度，取最小值之后，减去当前值可以得到收集的雨水数了，比如说我是1，0，2，那么收集的雨水就为1-0=1即可： ```Java class Solution { public int trap(int[] height) { int n = height.length; if (n == 0) { return 0; } int[] leftMax = new int[n]; leftMax[0] = height[0]; for (int i = 1; i < n; ++i) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); } int[] rightMax = new int[n]; rightMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; --i) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } int ans = 0; for (int i = 0; i < n; ++i) { ans += Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans; } } ``` ### 螺旋矩阵-? 给你一个 `m` 行 `n` 列的矩阵 `matrix` ，请按照 **顺时针螺旋顺序** ，返回矩阵中的所有元素。 #### **示例 1：** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/spiral1.jpg) ``` 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5] ``` #### **示例 2：** ![img](https://assets.leetcode.com/uploads/2020/11/13/spiral.jpg) ``` 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7] ``` **提示：** - `m == matrix.length` - `n == matrix[i].length` - `1 <= m, n <= 10` - `-100 <= matrix[i][j] <= 100` #### 分析 可以模拟螺旋矩阵的路径。初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入之前访问过的位置时，顺时针旋转，进入下一个方向。 判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵 visited\textit{visited}visited，其中的每个元素表示该位置是否被访问过。当一个元素被访问时，将 visited\textit{visited}visited 中的对应位置的元素设为已访问。 如何判断路径是否结束？由于矩阵中的每个元素都被访问一次，因此路径的长度即为矩阵中的元素数量，当路径的长度达到矩阵中的元素数量时即为完整路径，将该路径返回。 ```Java public class Solution1 { public List spiralOrder(int[][] matrix) { //1.list List list = new ArrayList<>(); //2.判断边界 if (matrix==null || matrix.length ==0 || matrix[0].length==0){ return list; } //3.获取行列 int rowMax = matrix.length,colMax=matrix[0].length; //4.判断方向数组 int[][] directions = {{0, 1}, {1, 0},{0,-1},{-1,0}}; boolean[][] flags = new boolean[rowMax][colMax]; //5.flag数组确定走过 row col nextrow nextcol int total = rowMax*colMax; int row = 0,col = 0; int directionIndex = 0;//方向索引 //6.for total 全部遍历完 for (int i = 0; i < total; i++) { //7.开始螺旋 加入list list.add(matrix[row][col]); //8.设置flag flags[row][col]=true; //9.设置nextrow nextcol int nextRow = row + directions[directionIndex][0]; int nextCol = col + directions[directionIndex][1]; if (nextRow < 0 || nextRow >= rowMax || nextCol < 0 || nextCol >=colMax || flags[nextRow][nextCol]){ directionIndex = (directionIndex + 1) % 4; } //10.判断是否超出边界顺时针转方向 //11.row col+方向数组 row += directions[directionIndex][0]; col += directions[directionIndex][1]; } return list; } } ``` ### 交易逆序对的总数 #### 描述 在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 `record`，返回其中存在的「交易逆序对」总数。 #### **示例 1:** ``` 输入：record = [9, 7, 5, 4, 6] 输出：8 解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。 ``` **限制：** ``` 0 <= record.length <= 50000 ``` #### 分析 预备知识 「归并排序」是分治思想的典型应用，它包含这样三个步骤： 分解： 待排序的区间为 [l,r][l, r][l,r]，令 m=⌊l+r2⌋m = \lfloor \frac{l + r}{2} \rfloorm=⌊ 2 l+r ⌋，我们把 [l,r][l, r][l,r] 分成 [l,m][l, m][l,m] 和 [m+1,r][m + 1, r][m+1,r] 解决： 使用归并排序递归地排序两个子序列 合并： 把两个已经排好序的子序列 [l,m][l, m][l,m] 和 [m+1,r][m + 1, r][m+1,r] 合并起来 在待排序序列长度为 111 的时候，递归开始「回升」，因为我们默认长度为 111 的序列是排好序的。 思路 那么求逆序对和归并排序又有什么关系呢？关键就在于「归并」当中「并」的过程。我们通过一个实例来看看。假设我们有两个已排序的序列等待合并，分别是 L={8,12,16,22,100}L = \{ 8, 12, 16, 22, 100 \}L={8,12,16,22,100} 和 R={9,26,55,64,91}R = \{ 9, 26, 55, 64, 91 \}R={9,26,55,64,91}。一开始我们用指针 lPtr = 0 指向 LLL 的首部，rPtr = 0 指向 RRR 的头部。记已经合并好的部分为 MMM。 ```Java public class Solution { public int reversePairs(int[] record) { int len = record.length; if (len < 2) { return 0; } int[] copy = new int[len]; for (int i = 0; i < len; i++) { copy[i] = record[i]; } int[] temp = new int[len]; return reversePairs(copy, 0, len - 1, temp); } private int reversePairs(int[] record, int left, int right, int[] temp) { if (left == right) { return 0; } int mid = left + (right - left) / 2; int leftPairs = reversePairs(record, left, mid, temp); int rightPairs = reversePairs(record, mid + 1, right, temp); if (record[mid] <= record[mid + 1]) { return leftPairs + rightPairs; } int crossPairs = mergeAndCount(record, left, mid, right, temp); return leftPairs + rightPairs + crossPairs; } private int mergeAndCount(int[] record, int left, int mid, int right, int[] temp) { for (int i = left; i <= right; i++) { temp[i] = record[i]; } int i = left; int j = mid + 1; int count = 0; for (int k = left; k <= right; k++) { if (i == mid + 1) { record[k] = temp[j]; j++; } else if (j == right + 1) { record[k] = temp[i]; i++; } else if (temp[i] <= temp[j]) { record[k] = temp[i]; i++; } else { record[k] = temp[j]; j++; count += (mid - i + 1); } } return count; } } ``` ## 3.二叉树 ### 二叉树的深度 #### 描述 某公司架构以二叉树形式记录，请返回该公司的层级数。 #### **示例 1：** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/1695101942-FSrxqu-image.png) ``` 输入：root = [1, 2, 2, 3, null, null, 5, 4, null, null, 4] 输出: 4 解释: 上面示例中的二叉树的最大深度是 4，沿着路径 1 -> 2 -> 3 -> 4 或 1 -> 2 -> 5 -> 4 到达叶节点的最长路径上有 4 个节点。 ``` **提示：** - `节点总数 <= 10000` #### 难度 容易 #### 分析 ##### DFS 简单来说，有两种思路解决，先说简单粗暴的递归，我们只要不断递归就能返回，递归是什么呢，打个比方就是说，1+1=2，2+2=4，那么这里呢，正着运算就是递归的回溯，反着来也就是递归了，也就是说我们并不知道多少+多少=4，我们就往上层走，好了解释完概念，我们步入正题，具体分几步走：1.确定边界，判空；2.直接返回方法吗？怎么返回，我们需要判断的是，我们递归的条件，我们需要深度，也就是根节点有左右节点就需要深度+1，直到没有所以： ```Java class Solution1 { public int calculateDepth(TreeNode root) { //临界值判定 if (root == null) { return 0; } //一直判断左子树 -》 右子树，直到没有子树为止，count+1 return Math.max(calculateDepth(root.left), calculateDepth(root.right) + 1);//返回左右子树的最大深度 } } ``` ##### BFS 这里我们可以采取广度优先，什么意思呢，也就是说我们只要确定完层数我们就可以确定深度；总体分几步走：1.确认边界；2.我们给定一个队列来存储这个二叉树，再通过一个队列来存子节点，我们只需要判断是否存在左右节点，就可以判定深度了： ```Java public class Solution2 { public int calculateDepth(TreeNode root) { if(root==null){ return 0; } //给一个计数的值 int count = 0; //定义一个队列 存储当前节点 LinkedList queue = new LinkedList(),tmp; queue.add(root); while(!queue.isEmpty()){ // 给tmp赋值每次都更新 tmp = new LinkedList(); for (TreeNode node : queue) { if(node.left!=null){ tmp.add(node.left); } if(node.right!=null){ tmp.add(node.right); } } queue = tmp; count++; } return count; } } ``` ### 之字形打印二叉树 #### 描述 一棵圣诞树记作根节点为 `root` 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照如下规则记录彩灯装饰结果： - 第一层按照从左到右的顺序记录。 - 除第一层外每一层的记录顺序均与上一层相反。即第一层为从左到右，第二层为从右到左。 #### **示例 1：** ![img](https://pic.leetcode.cn/1694758674-XYrUiV-剑指 Offer 32 - I_示例1.png) ``` 输入：root = [8,17,21,18,null,null,6] 输出：[[8],[21,17],[18,6]] ``` **提示：** - `节点总数 <= 1000` #### 难度 中等 #### 分析 首先我们需要知道我们拿到的是二叉树，先做边界判断，我们需要两个list 一个放最后返回的队列 一个放每个tree，只有这样我们才能通过一层一层的层序遍历；之后用for循环来达到循环的目的，在这个循环里，我们同样需要两个list 对于其值的size我们是确定的；之后遍历最上层的list树，遍历完后，将小树的传给大树，之后判断是否偶数，最后赋值给最上层队列即可： ```Java public class Solution1 { public List> decorateRecord(TreeNode root) { if(root==null){ return List.of(); } //1.创建两个list List> arrayList = new ArrayList<>(); List list = new ArrayList<>(); list.add(root); //2. 一个为最后返回的数组 一个是TreeNode //3.条件是for一个 直接判定是否为空 逐次相反 for (Boolean flag = false;!list.isEmpty();flag = !flag){ //4.设置两个list 一个是放树的 一个是放INterger List countList = new ArrayList<>(list.size()); List treeList = new ArrayList<>(); //5.遍历TreeNode for (TreeNode node : list) { //6.将值传给integer 然后判断左右是否为空 countList.add(node.val); if (node.left!=null) { treeList.add(node.left); } if (node.right!=null) { treeList.add(node.right); } } //7.赋值TreeNode list = treeList; //8.判断是否为偶数 if (flag) { Collections.reverse(countList); } //最后添加到最后返回的数组 arrayList.add(countList); } return arrayList; } } ``` ### 寻找二叉搜索树的目标节点 #### 描述 某公司组织架构以二叉搜索树形式记录，节点值为处于该职位的员工编号。请返回第 `cnt` 大的员工编号。 #### **示例 1：** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/1695101634-kzHKZW-image.png) ``` 输入：root = [7, 3, 9, 1, 5], cnt = 2 7 / \ 3 9 / \ 1 5 输出：7 ``` #### **示例 2：** ![img](https://pic.leetcode.cn/1695101636-ESZtLa-image.png) ``` 输入: root = [10, 5, 15, 2, 7, null, 20, 1, null, 6, 8], cnt = 4 10 / \ 5 15 / \ \ 2 7 20 / / \ 1 6 8 输出: 8 ``` **提示：** - 1 ≤ cnt ≤ 二叉搜索树元素个数 #### 分析 首先第一种方法，我们知道二叉搜索树的中序排序是正序排序的所以我们只要确定好正序还是倒序就可以了；正序的话你不能确定，只能等排序完后，去根据list的大小来获得值；而倒序，可以提前结束，也就是通过递归次数，我们每一次递归都-1来判断这个当前值是不是我们需要的，也就是它的上层数据： 倒序： ```Java public class Solution1 { int res,cnt; public int findTargetNode(TreeNode root, int cnt) { //先判断边界 this.cnt = cnt; //dfs 中序倒序 dfs(root); return res; } void dfs(TreeNode root) { //判断边界 if (root==null) { return; } //右边是否为空 不为空则递归 if (root.right!=null){ dfs(root.right); } if (cnt==0){ return; } if (--cnt==0){ res=root.val; } if (root.left!=null){ dfs(root.left); } } } ``` 正序： ```Java class Solution2{ ArrayList list = new ArrayList<>(); public int findTargetNode(TreeNode root, int cnt) { dfs(root); return list.get(list.size()-cnt); } void dfs(TreeNode root) { if(root==null)return; dfs(root.left); list.add(root.val); dfs(root.right); } } ``` ### 二叉树的最近公共祖先 #### 描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 [百度百科](https://baike.baidu.com/item/最近公共祖先/8918834?fr=aladdin)中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。” #### **示例 1：** ![img](https://assets.leetcode.com/uploads/2018/12/14/binarytree.png) ``` 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 ``` #### **示例 2：** ![img](https://assets.leetcode.com/uploads/2018/12/14/binarytree.png) ``` 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 ``` #### **示例 3：** ``` 输入：root = [1,2], p = 1, q = 2 输出：1 ``` **提示：** - 树中节点数目在范围 `[2, 105]` 内。 - `-109 <= Node.val <= 109` - 所有 `Node.val` `互不相同` 。 - `p != q` - `p` 和 `q` 均存在于给定的二叉树中。 #### 分析 首先，我们需要理解需要的是什么，也就是说这个问题其实就是两条链表求最近公共点，这样理解我们可以找到，但是做不出来；我们更应该分情况来讨论 ：1.我们节点为空或者p或者q任一为root 2.我们需要递归来遍历完左边和右边；判断左右哪边不为空，或者两边都不为空，当都不为空时，我们就直接返回root，左右只要判断一次即可： ```Java public class Solution1 { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //首先我们先判断是否p是否是当前节点 q是否是当前节点 if (root == null || root == q || root == p){ return root; } //递归左 递归右 TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left!=null && right!=null){ return root; } //如果左边有则返回左 if (left!=null){ return left; } //如果右边有则返回右 return left!=null ? left:right; } } ``` ### 二叉树中和为某一值的路径 #### 描述 给你二叉树的根节点 `root` 和一个整数目标和 `targetSum` ，找出所有 **从根节点到叶子节点** 路径总和等于给定目标和的路径。 **叶子节点** 是指没有子节点的节点。 #### **示例 1：** ![img](https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg) ``` 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]] ``` #### **示例 2：** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/pathsum2.jpg) ``` 输入：root = [1,2,3], targetSum = 5 输出：[] ``` #### **示例 3：** ``` 输入：root = [1,2], targetSum = 0 输出：[] ``` **提示：** - 树中节点总数在范围 `[0, 5000]` 内 - `-1000 <= Node.val <= 1000` - `-1000 <= targetSum <= 1000` #### 分析 dfs方法直接遍历分析好就行，主要是了解清除树遍历得深度优先和广度优先，你的思路就会打开很多： ```Java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { List> arrayList = new ArrayList<>(); int count; public List> pathTarget(TreeNode root, int target) { count = target; dfs(root,0,new ArrayList<>()); return arrayList; } private void dfs(TreeNode root, int num, ArrayList list) { //1.先判断边界 if (root==null){ return; } list.add(root.val); //2.判断是否满足条件 即num+root.val==count 同时左右均为空 if (num+root.val==count && root.left==null&& root.right==null){ arrayList.add(new ArrayList<>(list)); } //3.遍历左边 遍历右边 dfs(root.left,num+root.val,list); dfs(root.right,num+root.val,list); //4.移除最后一个元素 方便继续添加 list.remove(list.size()-1); } } ``` ### 二叉树的最大路径和 #### 描述 二叉树中的 **路径** 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 **至多出现一次** 。该路径 **至少包含一个** 节点，且不一定经过根节点。 **路径和** 是路径中各节点值的总和。 给你一个二叉树的根节点 `root` ，返回其 **最大路径和** 。 #### **示例 1：** ![img](https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg) ``` 输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6 ``` #### **示例 2：** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/exx2.jpg) ``` 输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42 ``` **提示：** - 树中节点数目范围是 `[1, 3 * 104]` - `-1000 <= Node.val <= 1000` #### 分析 我们的思路很明确，bfs直接，这里最重要的是要知道什么时候返回，官方的思路是根据贡献点，也就是说左右只有贡献大于0才加： ```Java public class Solution { private int max =Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); //2.dfs来写 return max; } private int dfs(TreeNode node) { if (node==null){ return 0; } int left = dfs(node.left); int right = dfs(node.right); int maxCount = left+right+node.val; max = Math.max(max,maxCount);//更新数据 return Math.max(node.val+Math.max(left,right),0); //最后递归回到最终返回 } } ``` ```Java class Solution { private int ans = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode node) { if (node == null) return 0; // 没有节点，和为 0 int lVal = dfs(node.left); // 左子树最大链和 int rVal = dfs(node.right); // 右子树最大链和 ans = Math.max(ans, lVal + rVal + node.val); // 两条链拼成路径 return Math.max(Math.max(lVal, rVal) + node.val, 0); // 当前子树最大链和 } } ``` ### 计算二叉树的右视图 #### 描述 给定一个二叉树的 **根节点** `root`，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 #### **示例 1:** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/tree.jpg) ``` 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] ``` #### **示例 2:** ``` 输入: [1,null,3] 输出: [1,3] ``` #### **示例 3:** ``` 输入: [] 输出: [] ``` **提示:** - 二叉树的节点个数的范围是 `[0,100]` - `-100 <= Node.val <= 100` #### 分析 很明确的答案：bfs广度优先，层序遍历，直接用队列做简单粗暴，每层取最后一个，while条件判空，一个for循环就可以找到需要的最右值： ```Java public class Solution1 { class Solution { public List rightSideView(TreeNode root) { ArrayList list = new ArrayList<>(); //边界判断 if (root == null) { return list; } //放入队列树里 Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } if (i == size-1) { list.add(node.val); } } // } return list; } } } ``` dfs深度优先: ```Java ArrayList list = new ArrayList<>(); public List rightSideView(TreeNode root) { dfs(root,0); return list; } private void dfs(TreeNode root, int width) { if (root==null){ return; } if (width==list.size()){ list.add(root.val); } width++; dfs(root.right,width); dfs(root.left,width); } ``` ## 4.链表 ### 反转链表+1 #### 描述 给你单链表的头节点 `head` ，请你反转链表，并返回反转后的链表。 #### **示例 1：** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/rev1ex1.jpg) ``` 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] ``` #### **示例 2：** ![img](https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg) ``` 输入：head = [1,2] 输出：[2,1] ``` #### **示例 3：** ``` 输入：head = [] 输出：[] ``` **提示：** - 链表中节点的数目范围是 `[0, 5000]` - `-5000 <= Node.val <= 5000` **进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？ #### 分析 ```Java /** * 解法一：迭代 * @param head * @return */ public ListNode reverseList(ListNode head) { //先创建头反转的链表 ListNode fir = null; //再创建指向原链表的链表 ListNode sec = head; //原链表不为空为条件 while (sec!=null) { //创建除头外的指针链表 ListNode next = sec.next; //将指向掉头 sec.next = fir; //重新赋值指向变化后的原链表的指针链表 fir = sec; //状态链表跟着改变 sec = next; } return fir; } /** * 解法2：递归 * @param head * @return */ public ListNode reverseList1(ListNode head) { //边界 if (head == null || head.next == null){ return head; } //递归 ListNode newNode = reverseList(head); //x的next的next=x head.next.next = head; //最前面的指空 head.next = null; return newNode; } ``` ## k个反转链表-1 #### 描述 给你链表的头节点 `head` ，每 `k` 个节点一组进行翻转，请你返回修改后的链表。 `k` 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 `k` 的整数倍，那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 #### **示例 1：** ![img](https://assets.leetcode.com/uploads/2020/10/03/reverse_ex1.jpg) ``` 输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5] ``` #### **示例 2：** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/reverse_ex2.jpg) ``` 输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5] ``` **提示：** - 链表中的节点数目为 `n` - `1 <= k <= n <= 5000` - `0 <= Node.val <= 1000` **进阶：**你可以设计一个只用 `O(1)` 额外内存空间的算法解决此问题吗？ #### 分析 ```Java public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(0); // 此处只是设置一个哨兵节点 dummy.next = head; // 哨兵节点的下一个指向首节点 ListNode pre = dummy; // 上一段的最后一个节点 节点初始化 ListNode end = dummy; // 本段最后一个节点 while (end.next != null) { // 此处是为了找到其中的 k 个子节点 for(int i = 0 ; i < k && end != null; i++){ end = end.next; } if(end == null){ // 如果直接到头了，那就说明没有满足 k 个 break; } ListNode start = pre.next; // 此处是为记录原始未反转段的起始节点 ListNode nextStart = end.next; // 记录下一个阶段 起始点 end.next = null; // 此处是为了进行后面的反转操作，断开此处链接,让后面反转操作知道截断点在哪里 pre.next = reverse(start); // 反转操作 start.next = nextStart; // 反转之后，start节点实际是已经最后一个节点了，为了和后面的划分段链接，让他的下一个节点连接上下一段的起始点即可 pre = start; // pre再次来到下一段的上一个节点，也就是本段的结尾点 end = pre; // 结束点，准备开始下一段的循环找 k 长度的段操作 } return dummy.next; // 返回最开始的哨兵 } private ListNode reverse(ListNode head){ ListNode pre = null; ListNode curr = head; while(curr != null){ // 交换操作 ListNode next = curr.next; curr.next = pre; pre = curr; curr = next; } return pre; // 返回哨兵，此处是新的翻转序列的起始节点 } ``` ## 删除排序链表中的重复元素 #### 描述 给定一个已排序的链表的头 `head` ， *删除所有重复的元素，使每个元素只出现一次* 。返回 *已排序的链表* 。 #### **示例 1：** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/list1.jpg) ``` 输入：head = [1,1,2] 输出：[1,2] ``` #### **示例 2：** ![img](https://assets.leetcode.com/uploads/2021/01/04/list2.jpg) ``` 输入：head = [1,1,2,3,3] 输出：[1,2,3] ``` **提示：** - 链表中节点数目在范围 `[0, 300]` 内 - `-100 <= Node.val <= 100` - 题目数据保证链表已经按升序 **排列** #### 分析 迭代做法 ```java public ListNode deleteDuplicates(ListNode head) { if(head == null){ return head; } ListNode newNode = head; while (newNode.next != null){ if (newNode.val == newNode.next.val){ newNode.next = newNode.next.next; }else { newNode = newNode.next; } } return head; } ``` 递归做法 ```Java public class lc83 { public ListNode deleteDuplicates(ListNode head) { if (head == null){ return head; } while (head.next!=null && head.val == head.next.val){ head.next = head.next.next; } head.next = deleteDuplicates(head.next); return head; } } ``` 变式[82. 删除排序链表中的重复元素 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/) ## 环形链表 #### 描述 给你一个链表的头节点 `head` ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 `next` 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。**注意：`pos` 不作为参数进行传递** 。仅仅是为了标识链表的实际情况。 *如果链表中存在环* ，则返回 `true` 。 否则，返回 `false` 。 #### **示例 1：** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist.png) ``` 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 ``` #### **示例 2：** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test2.png) ``` 输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。 ``` #### **示例 3：** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test3.png) ``` 输入：head = [1], pos = -1 输出：false 解释：链表中没有环。 ``` **提示：** - 链表中节点的数目范围是 `[0, 104]` - `-105 <= Node.val <= 105` - `pos` 为 `-1` 或者链表中的一个 **有效索引** 。 **进阶：**你能用 `O(1)`（即，常量）内存解决此问题吗？ #### 分析 龟兔赛跑快慢指针 + set的boolean来确定是否有环 ```Java public class Solution { public boolean hasCycle(ListNode head) { HashSet set = new HashSet<>(); while (head!=null){ if (!set.add(head)){ return true; } head = head.next; } return false; } } ``` ```Java if (head == null || head.next == null){ return false; } ListNode slow = head; ListNode fast = head.next; while(slow != fast){ if (fast.next == null){ return false; } head = head.next; fast = fast.next.next; slow = slow.next; } return true; ``` ## 两个链表的第一个公共节点 #### 描述 某教练同时带教两位学员，分别以链表 `l1`、`l2` 记录了两套核心肌群训练计划，节点值为训练项目编号。两套计划仅有前半部分热身项目不同，后续正式训练项目相同。请设计一个程序找出并返回第一个正式训练项目编号。如果两个链表不存在相交节点，返回 `null` 。 如下面的两个链表**：** [![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png)](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png) 在节点 `c1` 开始相交。 输入说明： `intersectVal` - 相交的起始节点的值。如果不存在相交节点，这一值为 0 `l1` - 第一个训练计划链表 `l2` - 第二个训练计划链表 `skip1` - 在 `l1` 中（从头节点开始）跳到交叉节点的节点数 `skip2` - 在 `l2` 中（从头节点开始）跳到交叉节点的节点数 程序将根据这些输入创建链式数据结构，并将两个头节点 `head1` 和 `head2` 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案 。 #### **示例 1：** [![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_1.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_1.png) ``` 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 解释：第一个正式训练项目编号为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 ``` #### **示例 2：** [![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_2.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_2.png) ``` 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Reference of the node with value = 2 解释：第一个正式训练项目编号为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。 ``` #### **示例 3：** [![img](https://gitee.com/oschina_72/picgo/raw/master/path/160_example_3.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_3.png) ``` 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：两套计划完全不同，返回 null。从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 ``` **注意：** - 如果两个链表没有交点，返回 `null`. - 在返回结果后，两个链表仍须保持原有的结构。 - 可假定整个链表结构中没有循环。 - 程序尽量满足 O(*n*) 时间复杂度，且仅用 O(*1*) 内存。 - 本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/ #### 分析 双指针 a+b-c = a+b-c,也就是说他们如果有公共的则一定相遇因为速度相同路程相同 ```Java class Solution { ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode A = headA,B = headB; while (A != B){ A = A != null ? A.next : headB; B = B != null ? B.next : headA; } return A; } } ``` ## 合并有序链表 #### 描述 给定两个以 **有序链表** 形式记录的训练计划 `l1`、`l2`，分别记录了两套核心肌群训练项目编号，请合并这两个训练计划，按训练项目编号 **升序** 记录于链表并返回。 **注意**：新链表是通过拼接给定的两个链表的所有节点组成的。 #### **示例 1：** ``` 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] ``` #### **示例 2：** ``` 输入：l1 = [], l2 = [] 输出：[] ``` #### **示例 3：** ``` 输入：l1 = [], l2 = [0] 输出：[0] ``` **提示：** ``` 0 <= 链表长度 <= 1000 ``` #### 分析 递归/迭代 ```Java public ListNode trainningPlan(ListNode l1, ListNode l2) { //递归 if(l1 == null){ return l1; }else if(l2 == null){ return l2; }else if(l1.val > l2.val){ l1.next = trainningPlan(l1.next,l2); return l1; }else { l2.next = trainningPlan(l1,l2.next); return l2; } } ``` ```Java ListNode l3 = new ListNode(-1); ListNode l4 = l3; while (l1!=null && l2 !=null){ if(l1.val >= l2.val){ l4.next = l1; l1 = l1.next; }else { l4.next = l2; l2 = l2.next; } l4 =l4.next; } l4.next = l1 == null ? l2 : l1; return l3.next; ``` ## [面试题 02.05. 链表求和](https://leetcode.cn/problems/sum-lists-lcci/) 中等 #### 描述 给定两个用链表表示的整数，每个节点包含一个数位。 这些数位是反向存放的，也就是个位排在链表首部。 编写函数对这两个整数求和，并用链表形式返回结果。 #### **示例：** ``` 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912 ``` **进阶：**思考一下，假设这些数位是正向存放的，又该如何解决呢? #### **示例：** ``` 输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295 输出：9 -> 1 -> 2，即912 ``` #### 分析 边变式，边模拟竖式加法 ```Java public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode l3 = new ListNode(-1),ans = l3; int t = 0; while(l1 != null || l2 != null || t != 0){ if (l1 != null){ t += l1.val; l1 = l1.next; } if (l2 != null){ t += l2.val; l2 = l2.next; } ans.next = new ListNode(t%10); ans = ans.next; t /= 10; } return l3.next; } ``` ## [234. 回文链表](https://leetcode.cn/problems/palindrome-linked-list/) 简单 #### 描述 给你一个单链表的头节点 `head` ，请你判断该链表是否为回文链表。如果是，返回 `true` ；否则，返回 `false` 。 **示例 1：** ![img](https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg) ``` 输入：head = [1,2,2,1] 输出：true ``` ##### **示例 2：** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/pal2linked-list.jpg) ``` 输入：head = [1,2] 输出：false ``` **提示：** - 链表中节点数目在范围`[1, 105]` 内 - `0 <= Node.val <= 9` #### 分析 简单题，只要判断一次即可确定，若没有回文则false ```Java class Solution { private ListNode frontPointer; private boolean recursivelyCheck(ListNode currentNode) { if (currentNode != null) { if (!recursivelyCheck(currentNode.next)) { return false; } if (currentNode.val != frontPointer.val) { return false; } frontPointer = frontPointer.next; } return true; } public boolean isPalindrome(ListNode head) { frontPointer = head; return recursivelyCheck(head); } } ``` ## [138. 随机链表的复制](https://leetcode.cn/problems/copy-list-with-random-pointer/) 中等 #### 描述 给你一个长度为 `n` 的链表，每个节点包含一个额外增加的随机指针 `random` ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的 **[深拷贝](https://baike.baidu.com/item/深拷贝/22785317?fr=aladdin)**。 深拷贝应该正好由 `n` 个 **全新** 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 `next` 指针和 `random` 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。**复制链表中的指针都不应指向原链表中的节点** 。 例如，如果原链表中有 `X` 和 `Y` 两个节点，其中 `X.random --> Y` 。那么在复制链表中对应的两个节点 `x` 和 `y` ，同样有 `x.random --> y` 。 返回复制链表的头节点。 用一个由 `n` 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 `[val, random_index]` 表示： - `val`：一个表示 `Node.val` 的整数。 - `random_index`：随机指针指向的节点索引（范围从 `0` 到 `n-1`）；如果不指向任何节点，则为 `null` 。 你的代码 **只** 接受原链表的头节点 `head` 作为传入参数。 #### **示例 1：** ![img](https://gitee.com/oschina_72/picgo/raw/master/path/e1.png) ``` 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] ``` #### **示例 2：** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e2.png) ``` 输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]] ``` #### **示例 3：** **![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e3.png)** ``` 输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]] ``` **提示：** - `0 <= n <= 1000` - `-104 <= Node.val <= 104` - `Node.random` 为 `null` 或指向链表中的节点。 #### 分析 ```Java public Node copyRandomList(Node head) { if (head == null) { return null; } for (Node node = head; node != null; node = node.next.next) { Node nodeNew = new Node(node.val); nodeNew.next = node.next; node.next = nodeNew; } for (Node node = head; node != null; node = node.next.next) { Node nodeNew = node.next; nodeNew.random = (node.random != null) ? node.random.next : null; } Node headNew = head.next; for (Node node = head; node != null; node = node.next) { Node nodeNew = node.next; node.next = node.next.next; nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null; } return headNew; } ```