二刷整合

数组：内存空间连续，数据类型统一，下标从0开始
二分查找

704

1. class Solution {
2.     public int search(int[] nums, int target) {
3.         // 方法一：暴力解法
4.         // for(int i = 0; i < nums.length; i++){
5.         //     if(nums[i] == target){//找到目标值
6.         //         return i;
7.         //     }
8.         // }
9.         // return -1;
10.         // 方法二：二分查找（元素有序且无重复元素），使用迭代，执行速度快，但是内存消耗大
11.         // return binarySearch(nums, target, 0, nums.length-1);
12.         // 方法三：二分查找，统一使用左闭右闭区间
13.         // 上来先处理边界条件
14.         if(target < nums[0] || target > nums[nums.length - 1]){
15.             return -1;
16.         }
17.         int left = 0;
18.         int right = nums.length - 1;//右闭区间
19.         int mid = (left + right) >> 1;
20.         while(left <= right){//因为取得数组区间左右都是闭的，所以取等号的时候也能满足条件，还不需要退出循环
21.             if(target == nums[mid]){
22.                 return mid;
23.             }else if(target < nums[mid]){
24.                 right = mid -1;//往左区间缩
25.             }else{
26.                 left = mid +1;
27.             }
28.             mid = (left + right) >> 1;
29.         }
30.         return -1;
31.     }
32.     // public int binarySearch(int[] nums, int target, int start, int end){
33.     //     int mid = (start+end)/2;
34.     //     int find = -1;
35.     //     if(start > end){//没有找到
36.     //         return -1;
37.     //     }
38.     //     if(target == nums[mid]){
39.     //         return mid;
40.     //     }else if(target < nums[mid]){
41.     //         find = binarySearch(nums, target, start, mid-1);
42.     //     }else{
43.     //         find = binarySearch(nums, target, mid+1, end);
44.     //     }
45.     //     return find;
46.     // }
47. }

复制代码

搜索插入位置

35

1. class Solution {
2.     public int searchInsert(int[] nums, int target) {
3.         // 有序数组，考虑用二分查找
4.         int left = 0;
5.         int right = nums.length - 1;
6.         int mid = (left + right) >> 1;
7.         if(target < nums[left]){
8.             return left;
9.         }
10.         if(target > nums[right]){
11.             return right + 1;
12.         }
13.         while(left <= right){
14.             if(target == nums[mid]){
15.                 return mid;
16.             }else if(target < nums[mid]){
17.                 right = mid -1;
18.             }else{
19.                 left = mid + 1;
20.             }
21.             mid = (left + right) >> 1;
22.         }
23.         return left;//找不到，返回需要插入的位置
24.     }
25. }

复制代码

在排序数组中查找元素的第一个和最后一个位置

34

1. class Solution {
2.     public int[] searchRange(int[] nums, int target) {
3.         // 非递减说明是升序的，但可以有重复元素
4.         int[] arr = {-1, -1};
5.         if(nums.length == 0){
6.             return arr;
7.         }
8.         int left = 0;
9.         int right = nums.length - 1;
10.         int mid = (left + right) >> 1;
11.         if(target < nums[left] || target > nums[right]){
12.             return arr;//边界值
13.         }
14.         int leftPoint;//目标数组的开始位置
15.         int rightPoint;//目标数组的结束位置
16.         while(left <= right){
17.             if(target == nums[mid]){
18.                 leftPoint = mid;
19.                 rightPoint = mid;
20.                 while(leftPoint >= 0 && target == nums[leftPoint]){
21.                     arr[0] = leftPoint;
22.                     leftPoint--;//向左寻找重复元素
23.                 }
24.                 while(rightPoint <= (nums.length - 1) && target == nums[rightPoint]){
25.                     arr[1] = rightPoint;
26.                     rightPoint++;//向右寻找重复元素
27.                 }
28.                 return arr;//返回找到的目标值的位置
29.             }else if(target < nums[mid]){
30.                 right = mid - 1;
31.             }else{
32.                 left = mid + 1;
33.             }
34.             mid = (left + right) >> 1;
35.         }
36.         return arr;//没有找到
37.     }
38. }

复制代码

69、x的平方根

1. class Solution {
2.     public int mySqrt(int x) {
3.         // 使用二分查找
4.         int left = 0;
5.         int right = x;
6.         int mid = (left + right) / 2;
7.         while(left <= right){
8.             if((long)mid * mid < x){
9.                 left = mid + 1;
10.             }else if((long)mid * mid > x){
11.                 right = mid - 1;
12.             }else{
13.                 return mid;
14.             }
15.             mid  = (left + right) / 2;
16.         }
17.         return right;
18.     }
19. }

复制代码

367、有效的完全平方数

1. class Solution {
2.     public boolean isPerfectSquare(int num) {
3.         int left = 0, right = num;
4.         while(left <= right){
5.             int mid = (left + right) >> 1;
6.             if((long) mid * mid == num){
7.                 return true;
8.             }else if((long) mid * mid < num){
9.                 left = mid + 1;
10.             }else{
11.                 right = mid - 1;
12.             }
13.         }
14.         return false;
15.     }
16. }

复制代码

移除元素

27

1. class Solution {
2.     public int removeElement(int[] nums, int val) {
3. // 原地移除，所有元素
4. // 数组内元素可以乱序
5.         // 方法一：暴力解法，不推荐，时间复杂度O(n^2)
6.         // int right = nums.length;//目标数组长度，右指针
7.         // for(int i = 0; i < right; i++){
8.         //     if(val == nums[i]){
9.         //         right--;//找到目标数值，目标数长度减一，右指针左移
10.         //         for(int j = i; j < right; j++){
11.         //             nums[j] = nums[j + 1];//数组整体左移一位（数组元素不能删除，只能覆盖）
12.         //         }
13.         //         i--;//左指针左移
14.         //     }
15.         // }
16.         // return right;
17.         // 方法二：快慢指针，时间复杂度O(n)
18.         // int solwPoint = 0;
19.         // for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
20.         //     if(nums[fastPoint] != val){
21.         //         nums[solwPoint] = nums[fastPoint];
22.         //         solwPoint++;
23.         //     }
24.         // }
25.         // return solwPoint;
26.         // 方法三：注意元素的顺序可以改变，使用相向指针，时间复杂度O(n)
27.         int rightPoint = nums.length - 1;
28.         int leftPoint = 0;
29.         while(rightPoint >= 0 && nums[rightPoint] == val){
30.             rightPoint--;
31.         }
32.         while(leftPoint <= rightPoint){
33.             if(nums[leftPoint] == val){
34.                 nums[leftPoint] = nums[rightPoint--];
35.             }
36.             leftPoint++;
37.             while(rightPoint >= 0 && nums[rightPoint] == val){
38.                 rightPoint--;
39.             }
40.         }
41.         return leftPoint;
42.     }
43. }

复制代码

26、删除排序数组中的重复项

1. class Solution {
2.     public int removeDuplicates(int[] nums) {
3. // 相对顺序一致，所以不能使用相向指针。
4. // 考虑使用快慢指针
5.         if(nums.length == 1){
6.             return 1;
7.         }
8.         int slowPoint = 0;
9.         for(int fastPoint = 1; fastPoint < nums.length; fastPoint++){
10.             if(nums[slowPoint] != nums[fastPoint]){
11.                 nums[++slowPoint] = nums[fastPoint];
12.             }
13.         }
14.         return slowPoint + 1;
15.     }
16. }

复制代码

283、移动零

1. class Solution {
2.     public void moveZeroes(int[] nums) {
3. // 要保持相对顺序，不能用相向指针
4.         int slowPoint = 0;
5.         for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
6.             if(nums[fastPoint] != 0){
7.                 nums[slowPoint++] = nums[fastPoint];//所有非零元素移到左边
8.             }
9.         }
10.         for(; slowPoint < nums.length; slowPoint++){
11.             nums[slowPoint] = 0;//把数组末尾置零
12.         }
13.     }
14. }

复制代码

844、比较含退格的字符串

1. class Solution {
2.     public boolean backspaceCompare(String s, String t) {
3.         // 从前往后的话不确定下一位是不是"#"，当前位需不需要消除，所以采用从后往前的方式
4.         int countS = 0;//记录s中"#"的数量
5.         int countT = 0;//记录t中"#"的数量
6.         int rightS = s.length() - 1;
7.         int rightT = t.length() - 1;
8.         while(true){
9.             while(rightS >= 0){
10.                 if(s.charAt(rightS) == '#'){
11.                     countS++;
12.                 }else{
13.                     if(countS > 0){
14.                         countS--;
15.                     }else{
16.                         break;
17.                     }
18.                 }
19.                 rightS--;
20.             }
21.             while(rightT >= 0){
22.                 if(t.charAt(rightT) == '#'){
23.                 countT++;
24.                 }else{
25.                     if(countT > 0){
26.                         countT--;
27.                     }else{
28.                         break;
29.                     }
30.                 }
31.                 rightT--;
32.             }
33.             if(rightT < 0 || rightS < 0){
34.                 break;
35.             }
36.             if(s.charAt(rightS) != t.charAt(rightT)){
37.                 return false;
38.             }
39.             rightS--;
40.             rightT--;
41.         }
42.         if(rightS == -1 && rightT == -1){
43.             return true;
44.         }
45.         return false;
46.     }
47. }

复制代码

有序数组的平方

977

1. class Solution {
2.     public int[] sortedSquares(int[] nums) {
3. // 用相向的双指针
4.         int[] arr = new int[nums.length];
5.         int index = arr.length - 1;
6.         int leftPoint = 0;
7.         int rightPoint = nums.length - 1;
8.         while(leftPoint <= rightPoint){
9.             if(Math.pow(nums[leftPoint], 2) > Math.pow(nums[rightPoint], 2)){
10.                 arr[index--] = (int)Math.pow(nums[leftPoint], 2);
11.                 leftPoint++;
12.             }else{
13.                 arr[index--] = (int)Math.pow(nums[rightPoint], 2);
14.                 rightPoint--;
15.             }
16.         }
17.         return arr;
18.     }
19. }

复制代码

长度最小的子数组

209

1. class Solution {
2.     public int minSubArrayLen(int target, int[] nums) {
3. // 注意是连续子数组
4.         // 使用滑动窗口，实际上还是双指针
5.         int left = 0;
6.         int sum = 0;
7.         int result = Integer.MAX_VALUE;
8.         for(int right = 0; right < nums.length; right++){//for循环固定的是终止位置
9.             sum += nums[right];
10.             while(sum >= target){
11.                 result = Math.min(result, right - left + 1);//记录最小的子数组
12.                 sum -= nums[left++];
13.             }
14.         }
15.         return result == Integer.MAX_VALUE ? 0 : result;
16.     }
17. }

复制代码

904、水果成篮

1. class Solution {
2.     public int totalFruit(int[] fruits) {
3. // 此题也可以使用滑动窗口
4.         int maxNumber = 0;
5.         int left = 0;
6.         Map<Integer, Integer> map = new HashMap<>();//用哈希表记录被使用的篮子数量，以及每个篮子中的水果数量
7.         for(int right = 0; right < fruits.length; right++){
8.             map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);//往篮子里面放水果
9.             while(map.size() > 2){//放进去的水果不符合水果类型
10.                 map.put(fruits[left], map.get(fruits[left]) - 1);
11.                 if(map.get(fruits[left]) == 0){
12.                     map.remove(fruits[left]);
13.                 }
14.                 left++;
15.             }
16.             maxNumber = Math.max(maxNumber, right - left + 1);
17.         }
18.         return maxNumber;
19.     }
20. }

复制代码

螺旋矩阵 II

59

1. class Solution {
2.     public int[][] generateMatrix(int n) {
3.         // 方法一：直接按序输出
4.         int[][] arr = new int[n][n];
5.          int top = 0;
6.          int buttom = n - 1;
7.          int left = 0;
8.          int right = n - 1;;
9.          int index = 1;
10.          while(left <= right && top <= buttom && index <= n*n){
11.              for(int i = left; i <= right; i++){
12.                  arr[top][i] = index++;
13.              }
14.              top++;
15.              for(int i = top; i <= buttom; i++){
16.                  arr[i][right] = index++;
17.              }
18.              right--;
19.              for(int i = right; i >= left; i--){
20.                  arr[buttom][i] = index++;
21.              }
22.              buttom--;
23.              for(int i = buttom; i >= top; i--){
24.                  arr[i][left] = index++;
25.              }
26.              left++;
27.          }
28.          return arr;
29.     }
30. }

复制代码

字符串：
反转字符串

344

1. class Solution {
2.     public List<Integer> spiralOrder(int[][] matrix) {
3.         int top = 0;
4.         int buttom = matrix.length - 1;
5.         int left = 0;
6.         int right = matrix[0].length - 1;
7.         List<Integer> list = new ArrayList<Integer>();
8.         while(left <= right && top <= buttom){
9.             for(int i = left; i <= right; i++){
10.                 if(top <= buttom)
11.                 list.add(matrix[top][i]);
12.             }
13.             top++;
14.             for(int i = top; i <= buttom; i++){
15.                 if(left <= right)
16.                 list.add(matrix[i][right]);
17.             }
18.             right--;
19.             for(int i = right; i >= left; i--){
20.                 if(top <= buttom)
21.                 list.add(matrix[buttom][i]);
22.             }
23.             buttom--;
24.             for(int i = buttom; i >= top; i--){
25.                 if(left <= right)
26.                 list.add(matrix[i][left]);
27.             }
28.             left++;
29.         }
30.         return list;
31.     }
32. }

复制代码

重复的子字符串

459

1. class Solution {
2.     public int[] spiralOrder(int[][] matrix) {
3.         if(matrix.length == 0){
4.             return new int[0];
5.         }
6.         int top = 0;
7.         int buttom = matrix.length - 1;
8.         int left = 0;
9.         int right = matrix[0].length - 1;
10.         int[] arr = new int[matrix.length*matrix[0].length];
11.         int index = 0;
12.         while(left <= right && top <= buttom){
13.             for(int i = left; i <= right; i++){
14.                 if(top <= buttom)
15.                 arr[index++] = matrix[top][i];
16.             }
17.             top++;
18.             for(int i = top; i <= buttom; i++){
19.                 if(left <= right)
20.                 arr[index++] = matrix[i][right];
21.             }
22.             right--;
23.             for(int i = right; i >= left; i--){
24.                 if(top <= buttom)
25.                 arr[index++] = matrix[buttom][i];
26.             }
27.             buttom--;
28.             for(int i = buttom; i >= top; i--){
29.                 if(left <= right)
30.                 arr[index++] = matrix[i][left];
31.             }
32.             left++;
33.         }
34.         return arr;
35.     }
36. }

复制代码

栈和队列：容器适配器，不提供迭代器
232、用栈实现队列

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode removeElements(ListNode head, int val) {
13. // 方法一：设置虚节点方式，推荐方式
14.         ListNode dummy = new ListNode(-1,head);
15.         ListNode pre = dummy;
16.         ListNode cur = head;
17.         while(cur != null){
18.             if(cur.val == val){
19.                 pre.next = cur.next;
20.             }else{
21.                 pre = cur;
22.             }
23.             cur = cur.next;
24.         }
25.         return dummy.next;
26.         // 方法二：时间复杂度O(n)，空间复杂度O(1)
27.         if(head == null){//空链表的情况
28.             return head;
29.         }
30.         while(head != null && head.val == val){//头结点为val的情况
31.             head = head.next;
32.         }
33.         ListNode temp = head;
34.         while(temp != null && temp.next != null){
35.             while(temp != null && temp.next != null && temp.next.val == val){
36.                 if(temp.next.next != null){
37.                     temp.next = temp.next.next;
38.                 }else{//最后一个节点为val的情况
39.                     temp.next = null;
40.                 }
41.                
42.             }
43.             temp = temp.next;
44.         }
45.         return head;
46.     }
47. }

复制代码

225、用队列实现栈

1. class MyLinkedList {
2.     int size;
3.     ListNode head;
4.     ListNode tail;
5. // 初始化链表,构建虚拟的头结点和尾节点
6.     public MyLinkedList() {
7.         size = 0;
8.         head = new ListNode(0);
9.         tail = new ListNode(0);
10.         head.next = tail;
11.         tail.prev = head;
12.     }
13.     public int get(int index) {
14.         ListNode cur = head;
15.         if(index > size - 1 || index < 0){
16.             return -1;
17.         }
18.         while(index >= 0){
19.             cur = cur.next;
20.             index--;
21.         }
22.         return cur.val;
23.     }
24.    
25.     public void addAtHead(int val) {
26.         addAtIndex(0,val);
28.     }
29.    
30.     public void addAtTail(int val) {
31.         addAtIndex(size,val);
32.     }
33.    
34.     public void addAtIndex(int index, int val) {
35.         if(index > size){
36.             return;
37.         }
38.         if(index < 0 ){
39.             index = 0;
40.         }
41.         size++;
42.         ListNode temp = new ListNode(val);
43.         ListNode cur = head;
44.         while(index > 0){
45.             cur = cur.next;
46.             index--;
47.         }
48.         temp.next = cur.next;
49.         cur.next = temp;
50.         temp.prev = cur;
51.     }
52.    
53.     public void deleteAtIndex(int index) {
54.         ListNode cur = head;
55.         if(index > size - 1 || index < 0){
56.             return;
57.         }
58.         while(index > 0){
59.             cur = cur.next;
60.             index--;
61.         }
62.         cur.next = cur.next.next;
63.         size--;
64.     }
65. }
66. class ListNode {
67.     int val;
68.     ListNode next;
69.     ListNode prev;
71.     public ListNode(int val) {
72.         this.val = val;
73.     }
74. }

复制代码

20、有效的括号

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode reverseList(ListNode head) {
13.         // 方法一：在头结点不断插入
14.         // if(head == null){
15.         //     return head;//空节点不需要反转
16.         // }
17.         // ListNode temp = head.next;//临时节点前移一位
18.         // head.next = null;//代反转链表的头结点拆出来
19.         // ListNode newHead = head;//待反转链表的头结点赋给新的链表        
20.         // while(temp != null){
21.         //     head = temp;//找出待反转链表的新头结点
22.         //     temp = temp.next;//临时节点前移一位
23.         //     head.next = null;//待反转链表的新头拆出来
24.         //     head.next = newHead;//待反转链表的心头指向新的链表
25.         //     newHead = head;//得到新的链表的新头
26.         // }
27.         // return newHead;
28.         // 方法二：压栈，利用栈的先入后出
29.         // if(head == null){
30.         //     return head;
31.         // }
32.         // Stack<ListNode> stack = new Stack<>();
33.         // ListNode temp = head;
34.         // while(head != null){
35.         //     temp = head.next;
36.         //     head.next = null;
37.         //     stack.push(head);
38.         //     head = temp;
39.         // }
40.         // ListNode newHead = new ListNode();
41.         // temp = newHead;
42.         // while(!stack.isEmpty()){
43.         //     temp.next = stack.pop();
44.         //     temp = temp.next;
45.         // }
46.         // return newHead.next;
47.         // 方法三：递归
48.         return reverse(null, head);
49.         // 方法四：从后往前递归
50.         // if(head == null){
51.         //     return null;
52.         // }
53.         // if(head.next == null){
54.         //     return head;
55.         // }
56.         // ListNode newHead = reverseList(head.next);
57.         // head.next.next = head;
58.         // head.next = null;
59.         // return newHead;
61.     }
62.     public ListNode reverse(ListNode pre, ListNode cur){
63.         if(cur == null){
64.             return pre;
65.         }
66.         ListNode temp = cur.next;
67.         cur.next = pre;
68.         return reverse(cur,temp);
69.     }
70. }

复制代码

1047、删除字符串中的所有相邻重复项

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode swapPairs(ListNode head) {
13.         // 方法一：从前往后进行迭代
14.         // if(head == null){
15.         //     return null;
16.         // }
17.         // if(head.next == null){
18.         //     return head;
19.         // }
20.         // ListNode temp = head.next;//依次记录偶数节点的位置
21.         // head.next = head.next.next;//交换相邻的节点
22.         // temp.next = head;
23.         // temp.next.next = swapPairs(temp.next.next);//迭代交换下一个相邻的节点
24.         // return temp;
25.         // 方法二：双指针
26.         if(head == null){
27.             return null;
28.         }
29.         if(head.next == null){
30.             return head;
31.         }
32.         ListNode temp = head.next;
33.         ListNode pre = head.next;//记录新的头结点
34.         while(temp != null){
35.             head.next = head.next.next;//交换相邻的节点
36.             temp.next = head;
37.             if(head.next == null || head.next.next == null){
38.                 break;
39.             }else{
40.                 head = head.next;//指向下一个相邻节点的奇数节点
41.                 temp.next.next = temp.next.next.next;//上一个相邻节点的偶数节点指向下一个节点的偶数节点
42.                 temp = head.next;//下一个相邻节点的偶数节点
43.             }  
44.         }
45.         return pre;
46.     }
47. }

复制代码

150、逆波兰表达式求值

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode removeNthFromEnd(ListNode head, int n) {
13.         // 方法一：快慢指针，返回头结点说明head的头结点不能动，所以把链表的地址赋给另外一个对象
14.         // 添加虚拟头结点，方便操作。比如需要删除的是头结点的时候不需要单独考虑这种特殊情况
15.         ListNode dummyHead = new ListNode();
16.         dummyHead.next = head;
17.         ListNode cur = dummyHead;
18.         ListNode temp = dummyHead;
19.         for(int i = 0; i < n; i++){
20.             temp = temp.next;
21.         }
22.         while(temp.next != null){
23.             cur = cur.next;
24.             temp = temp.next;
25.         }
26.         cur.next = cur.next.next;
27.         return dummyHead.next;
28.     }
29. }

复制代码

239、滑动窗口最大值
单调队列

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode(int x) {
7. *         val = x;
8. *         next = null;
9. *     }
10. * }
11. */
12. public class Solution {
13.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
14.         if(headA == null || headB == null){
15.             return null;
16.         }
17.         ListNode dummyHeadA = headA;
18.         int countA = 0;
19.         int countB = 0;
20.         ListNode dummyHeadB = headB;
21.         while(dummyHeadA.next != null){
22.             dummyHeadA = dummyHeadA.next;
23.             countA++;
24.         }
25.         while(dummyHeadB.next != null){
26.             dummyHeadB = dummyHeadB.next;
27.             countB++;
28.         }
29.         if(dummyHeadA != dummyHeadB){
30.             return null;//尾节点不相交则说明不相交
31.         }
32.         dummyHeadA = headA;
33.         dummyHeadB = headB;
34.         int index = (countA - countB) > 0 ? (countA - countB) : -(countA - countB);//两个链表的长度差
35.         for(int i = 0; i < index; i++){//让较长的链表先移动index位
36.             if((countA - countB) > 0){
37.                 dummyHeadA = dummyHeadA.next;
38.             }else{
39.                 dummyHeadB = dummyHeadB.next;
40.             }
41.         }
42.         while(dummyHeadA != dummyHeadB){//两个链表逐次向前移动，找出相交的第一个节点
43.             dummyHeadA = dummyHeadA.next;
44.             dummyHeadB = dummyHeadB.next;
45.         }
46.         return dummyHeadA;
47.     }
48. }

复制代码

347、前 K 个高频元素
优先级队列，大顶堆，小顶堆

1. /**
2. * Definition for singly-linked list.
3. * class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode(int x) {
7. *         val = x;
8. *         next = null;
9. *     }
10. * }
11. */
12. public class Solution {
13.     public ListNode detectCycle(ListNode head) {
14.         ListNode slow = head;
15.         ListNode fast = head;
16.         int count = 0;
17.         while(fast != null && fast.next != null){//判断是否有环
18.             fast = fast.next.next;
19.             slow = slow.next;
20.             count++;
21.             if(fast == slow){
22.         // 找环的入口
23.                 while(head != slow){
24.                     head = head.next;
25.                     slow = slow.next;
26.                 }
27.                 return head;
28.             }
29.         }
30.         
31.         return null;
32.     }
33. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！