递归和分治

剑指Offer 10- I.斐波那契数列 （简单）

递归

  1. class Solution {
  2.     // 备忘录
  3.     public int[] map = new int[101];
  4.     public int fib(int n) {
  5.        Arrays.fill(map, -1);
  6.        return doFib(n);
  7.     }
  9.     private int doFib(int n) {
  10.         // 找出重复子问题 => 写出递归公式 -> 写出终止条件
  11.         // 终止条件
  12.         if(n == 0 || n == 1) {
  13.             return n;
  14.         }
  15.         // 剪枝
  16.         if(map[n] != -1) {
  17.             return map[n];
  18.         } 
  19.         map[n] = (doFib(n - 1) + doFib(n - 2)) % 1000000007;
  20.         return map[n];
  21.     }
  22. }

动态规划

  1. class Solution {
  2.     public int fib(int n) {
  3.         if(n == 0 || n == 1) {
  4.             return n;
  5.         }
  6.         int[] sum = new int[n+1];
  7.         sum[0] = 0;
  8.         sum[1] = 1;
  9.         for(int i = 2; i <= n; i++) {
  10.             sum[i] = (sum[i - 1] + sum[i - 2]) % 1000000007;
  11.         }
  12.         return sum[n];
  13.     }
  14. }

剑指Offer 10- II.青蛙跳台阶问题（简单）

递归

  1. class Solution {
  2.     private int[] map = new int[101]; 
  3.     public int numWays(int n) {
  4.         // 递归公式 f(n) = f(n - 1) + f(n - 2); f(0) = f(1) = 1, f(2) = 2;
  5.         Arrays.fill(map, -1);
  6.         return doNumWays(n);
  7.     }
  9.     public int doNumWays(int n) {
  10.         // 递归公式 f(n) = f(n - 1) + f(n - 2); f(0) = f(1) = 1, f(2) = 2;
  11.         if(n == 0 || n == 1) {
  12.             return 1;
  13.         }
  14.         if(n == 2) {
  15.             return 2;
  16.         }
  17.         if(map[n] != -1) {
  18.             return map[n];
  19.         }
  20.         map[n] = (doNumWays(n -1) + doNumWays(n -2)) % 1000000007;
  21.         return map[n];
  22.     }
  23. }

动态规划

  1. class Solution {
  2.     public int numWays(int n) {
  3.         if(n == 0 || n == 1) {
  4.             return 1;
  5.         }
  6.         int n1 = 1, n2 = 1, sum = 1;
  7.         for(int i = 2; i <= n; i++) {
  8.             n1 = n2;
  9.             n2 = sum;
  10.             sum = (n1 + n2) % 1000000007;
  11.         } 
  12.         return sum;
  13.     }
  14. }

面试题08.01.三步问题 （简单）

递归+剪枝

  1. class Solution {
  2.     public int waysToStep(int n) {
  3.         // 递归公式: f(0) = 1, f(1) = 1, f(2) = f(0) + f(1), f(3) = f(0) + f(1) + f(2), f(4) = f(3) + f(2) + f(1)
  4.         // f(n) = f(n - 1) + f(n - 2) + f(n - 3)
  5.         long[] map = new long[n+1];
  6.         Arrays.fill(map, -1);
  7.         return (int)doWaysToStep(n, map); 
  8.     }
  10.     private long doWaysToStep(int n, long[] map) {
  11.         if(n == 0) {
  12.             return 1;
  13.         }
  14.         if(n == 1 || n == 2) {
  15.             return n;
  16.         }
  17.         if(map[n] != -1) {
  18.             return map[n];
  19.         }
  20.         map[n] = (doWaysToStep(n -1, map) + doWaysToStep(n -2, map) + doWaysToStep(n - 3, map)) % 1000000007;
  21.         return map[n];
  22.     }
  23. }

动态规划

  1. class Solution {
  2.     public int waysToStep(int n) {
  3.         // 递归公式: f(0) = 1, f(1) = 1, f(2) = f(0) + f(1), f(3) = f(0) + f(1) + f(2), f(4) = f(3) + f(2) + f(1)
  4.         // f(n) = f(n - 1) + f(n - 2) + f(n - 3)
  5.         if(n == 1 || n == 2) {
  6.             return n;
  7.         }
  8.         int n1 = 0, n2 = 1, sum = 2;
  9.         for(int i = 3; i <= n; i++) {
  10.             sum = (sum[i - 1] + sum[i - 2] + sum[i - 3]) % 1000000007;
  11.         }
  12.         return (int)sum[n]; 
  13.     }
  14. }

剑指Offer 06.从尾到头打印链表 （简单）

递归

  1. class Solution {
  2.     public int[] reversePrint(ListNode head) {
  3.         return reversePrint(head, 0);
  4.     }
  6.     public int[] reversePrint(ListNode node, int count) {
  7.         if(node == null) {
  8.             return new int[0];
  9.         }
  10.         if(node.next != null) {
  11.             int[] array = reversePrint(node.next, count + 1);
  12.             array[array.length - count - 1] = node.val;
  13.             return array;
  14.         } else {
  15.             int[] array = new int[count + 1];
  16.             array[0] = node.val;
  17.             return array;
  18.         }
  19.     }
  20. }

剑指Offer 24.反转链表 （简单）

递归

  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         // 注意边界条件
  4.          if(head == null || head.next == null) {
  5.             return head;
  6.         }
  7.         ListNode newHead = reverseList(head.next);
  8.         head.next.next = head;
  9.         head.next = null;
  10.         return newHead;      
  11.     }
  12. }

剑指Offer 16.数值的整数次方 （中等）

快速幂解析

题解：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/

  1. class Solution {
  2.     public double myPow(double x, int n) {
  3.         if(x == 0) {
  4.             return 0;
  5.         }
  6.         long b = n;
  7.         double res = 1.0;
  8.         if(n < 0) {
  9.             x = 1 / x;
  10.             b = -b; 
  11.         }
  12.         while(b > 0) {
  13.             // (b & 1) == 1 表示b为奇数
  14.             if((b & 1) == 1) {
  15.                 res *= x;
  16.             } 
  17.             x *= x;
  18.             // b 右移一位，等价于 b /= 2;
  19.             b >>= 1;
  20.         } 
  21.         return res;
  22.     }
  23. }

递归

解题思路：
递归分治和排序-习题解析-week03 - 图1

Java中因为n的最小值可以取到Integer.MIN_VALUE，如果直接取它的相反数的话还是它自己，会导致堆栈溢出，因此提一个x出来，具体看代码

  1. class Solution {
  2.     public double myPow(double x, int n) {
  3.         if(n == 0) {
  4.             return 1;
  5.         } else if (n < 0) {
  6.             return 1 / (x * myPow(x, -n - 1));
  7.         } else if(n % 2 == 0) {
  8.             return myPow(x * x, n / 2);
  9.         } else {
  10.             return x * myPow(x, n - 1);
  11.         }
  12.     }
  13. }

面试题08.05.递归乘法 （中等）

迭代+移位解法

  1. class Solution {
  2.     public int multiply(int A, int B) {
  3.         if(A == 0 || B == 0) {
  4.             return 0;
  5.         }
  6.         // 优化点：保持A为较大值，这样可以减少B向右移位的次数。
  7.         if(A > B) {
  8.             int t = A;
  9.             A = B;
  10.             B = t;
  11.         }
  12.         int res = 0;
  13.         long b = A;
  14.         // 利用移位操作来计算，将A作为基数，A * B，相当于A累加B次
  15.         // 当B为偶数时，A * B 等价于 A 向左移动 B/2 位，B =/ 2 => B >>= 1
  16.         // 当B为奇数时，等价于 A + A * (B-1)，此时(B-1)为偶数
  17.         while(B > 0) {
  18.             if((B & 1) == 1) {
  19.                 res += b;
  20.             }
  21.             b <<= 1;
  22.             B >>= 1; 
  23.         }
  24.         return res;
  25.     }
  26. }

递归+移位解法

  1. class Solution {
  2.     public int multiply(int A, int B) {
  3.         if(A == 0 || B == 0) {
  4.             return 0;
  5.         }
  6.         if((B & 1) == 1) {
  7.             return A + multiply(A, B - 1);
  8.         } else {
  9.             return multiply(A <<= 1, B >>= 1);
  10.         }
  11.     }
  12. }

排序

面试题10.01.合并排序的数组 （简单）

逆向双指针

  1. class Solution {
  2.     public void merge(int[] A, int m, int[] B, int n) {
  3.         // 边界条件
  4.         if(m == 0) {
  5.             for(int i = 0; i < n; i++) {
  6.                 A[i] = B[i];
  7.             }
  8.         }        
  9.         // 逆向双指针
  10.         int aIdx = m - 1, bIdx = n - 1, i = (m + n) - 1;
  11.         while(aIdx >= 0 && bIdx >= 0) {
  12.             if(A[aIdx] >= B[bIdx]) {
  13.                 A[i--] = A[aIdx--];
  14.             } else {
  15.                 A[i--] = B[bIdx--];
  16.             }
  17.         }
  19.         while(bIdx >= 0) {
  20.             A[i--] = B[bIdx--];
  21.         }
  22.     }
  23. }

迭代

  1. class Solution {
  2.     public void merge(int[] A, int m, int[] B, int n) {
  3.         int[] tmp = new int[m + n];
  4.         int aIdx = 0, bIdx = 0, i = 0;
  5.         while(aIdx < m && bIdx < n) {
  6.             while(aIdx < m && A[aIdx] <= B[bIdx]) {
  7.                 tmp[i++] = A[aIdx++];
  8.             } 
  10.             while(bIdx < n && A[aIdx] > B[bIdx]) {
  11.                 tmp[i++] = B[bIdx++];
  12.             }
  13.         }
  14.         while(aIdx < m) {
  15.             tmp[i++] = A[aIdx++];
  16.         } 
  18.         while(bIdx < n) {
  19.             tmp[i++] = B[bIdx++];
  20.         }
  22.         for(int j = 0; j < m + n; j++) {
  23.             A[j] = tmp[j];
  24.         }
  25.     }
  26. }

21.合并两个有序链表 （简单）

解题思路：虚拟头结点+迭代

  1. class Solution {
  2.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  3.         if(l1 == null) {
  4.             return l2;
  5.         }
  6.         if(l2 == null) {
  7.             return l1;
  8.         }
  10.         ListNode newHead = new ListNode(), p = newHead;
  11.         while(l1 != null && l2 != null) {
  12.             if(l1.val >= l2.val) {
  13.                 p.next = l2;
  14.                 l2 = l2.next;
  15.             } else {
  16.                 p.next = l1;
  17.                 l1 = l1.next;
  18.             }
  19.             p = p.next;
  20.         }
  22.         if(l1 != null) {
  23.             p.next = l1;
  24.         }
  26.         if(l2 != null) {
  27.             p.next = l2;
  28.         }
  30.         return newHead.next;
  31.     }
  32. }

242.有效的字母异位词（简单）

排序

解题思路：分别转成字符数组后，通过调用 Java API Arrays#sort() 进行排序，然后直接比对。

  1. class Solution {
  2.     public boolean isAnagram(String s, String t) {
  3.         if(s.length() != t.length()) {
  4.             return false;
  5.         }
  7.         char[] a = s.toCharArray();
  8.         char[] b = t.toCharArray();
  10.         Arrays.sort(a);
  11.         Arrays.sort(b);
  13.         return Arrays.equals(a, b);
  14.     }
  15. }

时间复杂度：O(nlogn)
空间复杂度：O(logn)

哈希表

解题思路：因为输入的字符串只包含小写字母，利用哈希表的特性，遍历字符串s，记录字符串s中字母出现的次数，然后遍历字符串t，对哈希表中出现的字母次数减一，最后遍历哈希表，不存在非0的值，就是有效的字母异位词。

  1. class Solution {
  2.     public boolean isAnagram(String s, String t) {
  3.         if(s.length() != t.length()) {
  4.             return false;
  5.         }
  7.         int size = s.length();
  8.         // 字符串只包含小写字母，那么可以定义一个大小为26的int类型的数组，构成一个哈希表
  9.         int[] map = new int[26];
  10.         for(int i = 0; i < size; i++) {
  11.             map[s.charAt(i) - 'a']++;
  12.         }
  14.         for(int i = 0; i < size; i++) {
  15.             map[t.charAt(i) - 'a']--;
  16.         }
  18.         for(int i = 0; i < map.length; i++) {
  19.             if(map[i] > 0) {
  20.                 return false;
  21.             }
  22.         }
  23.         return true;
  24.     }
  25. }

进阶写法：

  1. class Solution {
  2.     public boolean isAnagram(String s, String t) {
  3.         if (s.length() != t.length()) {
  4.             return false;
  5.         }
  6.         char[] s1 = s.toCharArray();
  7.         char[] t1 = t.toCharArray();
  8.         char[] counters = new char[26];
  9.         char[] countert = new char[26];
  10.         for (int i = 0; i < s1.length; i++) {
  11.             counters[s1[i] - 'a']++;
  12.             countert[t1[i] - 'a']++;
  13.         }
  14.         for (int i = 0; i < counters.length; i++) {
  15.             if (counters[i] != countert[i]) {
  16.                 return false;
  17.             }
  18.         }
  19.         return true;
  20.     }
  21. }

时间复杂度：O(n)
空间复杂度：O(1)

1502.判断能否形成等差数列（简单）

排序

解题思路：先排序，遍历计算任意相邻项的差，存在不同，则不是等差数列

  1. class Solution {
  2.     public boolean canMakeArithmeticProgression(int[] arr) {
  3.         Arrays.sort(arr);
  4.         int length = arr.length;
  5.         int diff = arr[1] - arr[0];
  6.         for(int i = 2; i < length; i++) {
  7.             int tmp = arr[i] - arr[i -1];
  8.             if(diff != tmp) {
  9.                 return false;
  10.             }
  11.         }
  12.         return true;
  13.     }
  14. }

时间复杂度：O(n)
空间复杂度：O(1)

等差数列公式

解题思路：先排序，等差数列需满足：a(i) * 2 = a(i -1) + a(i + 1)

  1. class Solution {
  2.     public boolean canMakeArithmeticProgression(int[] arr) {
  3.         Arrays.sort(arr);
  4.         for(int i = 1; i < arr.length - 1; i++) {
  5.             // 等差数列数组应满足：a(i) * 2 = a(i -1) + a(i + 1)
  6.             if(arr[i] * 2 != (arr[i -1] + arr[i + 1])) {
  7.                 return false;
  8.             }
  9.         }
  10.         return true;
  11.     }
  12. }

时间复杂度：O(n)
空间复杂度：O(1)

56.合并区间（中等）

解题思路：

  1. class Solution {
  2.     public int[][] merge(int[][] intervals) {
  3.         // 边界条件
  4.         if(intervals.length == 0) {
  5.             return new int[0][2];
  6.         }
  7.         // 以左端点排序
  8.         Arrays.sort(intervals, (interval1, interval2) -> interval1[0] - interval2[0]);
  10.         List<int[]> merged = new ArrayList<>();
  11.         for(int i = 0; i < intervals.length; i++) {
  12.             int L = intervals[i][0], R = intervals[i][1];
  13.             if(merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
  14.                 merged.add(new int[]{L, R});
  15.             } else {
  16.                 merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
  17.             }
  18.         }
  19.         return merged.toArray(new int[merged.size()][]);
  20.     }
  21. }
  1. class Solution {
  2.     public int[][] merge(int[][] intervals) {
  3.         // 先按照区间起始位置排序
  4.         Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
  5.         // 遍历区间
  6.         int[][] res = new int[intervals.length][2];
  7.         int idx = -1;
  8.         for (int[] interval: intervals) {
  9.             // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
  10.             // 则不合并，直接将当前区间加入结果数组。
  11.             if (idx == -1 || interval[0] > res[idx][1]) {
  12.                 res[++idx] = interval;
  13.             } else {
  14.                 // 反之将当前区间合并至结果数组的最后区间
  15.                 res[idx][1] = Math.max(res[idx][1], interval[1]);
  16.             }
  17.         }
  18.         return Arrays.copyOf(res, idx + 1);
  19.     }
  20. }

剑指Offer 21.调整数组顺序使奇数位于偶数前面 （简单）

首尾指针

解题思路：首尾指针，首指针遍历直至找到偶数，尾指针遍历直至找到奇数，然后交换首尾指针指向的数。

  1. class Solution {
  2.     public int[] exchange(int[] nums) {
  3.         int p = 0, q = nums.length - 1;
  4.         while(p <= q) {
  5.             while(p <= q && (nums[p] & 1) == 1) {
  6.                 p++;
  7.             }
  8.             while(p <= q && (nums[q] & 1) != 1) {
  9.                 q--;
  10.             }
  11.             if(p > q) {
  12.                 break;
  13.             }
  14.             int tmp = nums[p];
  15.             nums[p] = nums[q];
  16.             nums[q] = tmp;
  17.             p++;
  18.             q--;
  19.         }
  20.         return nums;
  21.     }
  22. }

时间复杂度：O(n/2) => O(n)
空间复杂度：O(1)

快慢指针

解题思路：设置快慢指针，快慢指针往前遍历，遇到奇数就交换，遇到偶数，快指针往前一步，直至快指针遍历完成。

  1. class Solution {
  2.     public int[] exchange(int[] nums) {
  3.         // 快慢指针
  4.         int slow = 0, fast = 0;
  5.         while(fast < nums.length) {
  6.             if((nums[fast] & 1) == 1) {
  7.                 int tmp = nums[slow];
  8.                 nums[slow] = nums[fast];
  9.                 nums[fast] = tmp;
  10.                 fast++;
  11.                 slow++;
  12.             } else {
  13.                 fast++;
  14.             }
  15.         }
  16.         return nums;
  17.     }
  18. }

时间复杂度：O(n)
空间复杂度：O(1)

75.颜色分类（中等）

冒泡排序

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         // 冒泡排序
  4.         for(int i = 0; i < nums.length; i++) {
  5.             // 标识有无数据交换
  6.             boolean flag = false;
  7.             for(int j = 0; j < nums.length - i -1; j++) {
  8.                 if(nums[j] > nums[j + 1]) {
  9.                     int tmp = nums[j];
  10.                     nums[j] = nums[j + 1];
  11.                     nums[j + 1] = tmp;
  12.                     flag = true;
  13.                 }
  15.             }
  16.             // 小优化，无数据交换证明已排序好
  17.             if(!flag) {
  18.                 return;
  19.             }
  20.         }
  21.     }
  22. }

单指针遍历

解题思路：遍历，先将0移至数组前，然后将1移至数组中0的后面

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         // 单指针解法
  4.         int ptr = 0;
  5.         // 遍历，将0移至数组前面
  6.         for(int i = 0; i < nums.length; i++) {
  7.             if(nums[i] == 0) {
  8.                 int tmp = nums[ptr];
  9.                 nums[ptr] = nums[i];
  10.                 nums[i] = tmp;
  11.                 ptr++; 
  12.             }
  13.         }
  15.         // 遍历，将1移至数组0后面
  16.         for(int i = ptr; i < nums.length; i++) {
  17.             if(nums[i] == 1) {
  18.                 int tmp = nums[ptr];
  19.                 nums[ptr] = nums[i];
  20.                 nums[i] = tmp;
  21.                 ptr++; 
  22.             }
  23.         }
  24.     }
  25. }

时间复杂度：O(n)
空间复杂度：O(1)

首尾双指针遍历

解题思路：跟单指针遍历的思路是一样的，通过首尾双指针，双向遍历，先将2交换至数组后面，在所有2都交换完毕后，将首指针重置，重新双向遍历，将1交换至2后面。

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         // 首尾双指针
  4.         int head = 0, tail = nums.length - 1;
  5.         // 先将2交换至数组尾部
  6.         while(head <= tail) {
  7.             if(nums[head] != 2) {
  8.                 head++;
  9.                 continue;
  10.             }
  11.             if(nums[tail] == 2) {
  12.                 tail--;
  13.                 continue;
  14.             }
  15.             swap(nums, head, tail);
  16.         }
  17.         // 重置首指针，尾指针保持不变
  18.         head = 0;
  19.         // 重新遍历，交换尾指针
  20.         while(head <= tail) {
  21.             if(nums[head] != 1) {
  22.                 head++;
  23.                 continue;
  24.             }
  25.             if(nums[tail] == 1) {
  26.                 tail--;
  27.                 continue;
  28.             }
  29.             swap(nums, head, tail);
  30.         }
  31.     }
  33.     private void swap(int[] nums, int p, int q) {
  34.         int tmp = nums[p];
  35.         nums[p] = nums[q];
  36.         nums[q] = tmp;
  37.     }
  38. }

时间复杂度：O(n)
空间复杂度：O(1)

首尾双指针解法二

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         // 双指针解法
  4.         int head = 0, tail = nums.length -1, size = nums.length;
  5.         for(int i = 0; i < size; i++) {
  6.             // 使用while是为了将数组前的2都交换至数组尾部，处理类似这种的特殊情况：[2,0,2,1,1,2]
  7.             while(i < tail && nums[i] == 2) {
  8.                 swap(nums, i, tail);
  9.                 tail--;
  10.             }
  12.             if(nums[i] == 0) {
  13.                 swap(nums, i, head);
  14.                 head++;
  15.             }
  16.         }
  17.     }
  19.     private void swap(int[] nums, int p, int q) {
  20.         int tmp = nums[p];
  21.         nums[p] = nums[q];
  22.         nums[q] = tmp;
  23.     }
  24. }

时间复杂度：O(n)
空间复杂度：O(1)

147.对链表进行插入排序（中等）

头插法

解题思路：

  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 insertionSortList(ListNode head) {
  13.         ListNode newHead = new ListNode(Integer.MIN_VALUE), p = head;
  14.         while(p != null) {
  15.             ListNode tmp = p.next;
  16.             ListNode cur = newHead;
  17.             while(cur.next != null && cur.next.val <= p.val) {
  18.                 cur = cur.next;
  19.             }
  20.             p.next = cur.next;
  21.             cur.next = p;
  22.             p = tmp; 
  23.         }
  24.         return newHead.next;
  25.     }
  26. }

时间复杂度：O(递归分治和排序-习题解析-week03 - 图2)
空间复杂度：O(1)

归并排序

解题思路：归并排序，利用递归来实现

  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 insertionSortList(ListNode head) {
  13.         // 边界条件
  14.         if(head == null || head.next == null) {
  15.             return head;
  16.         }
  17.         // 归并排序
  18.         // 1. 找到中间节点 
  19.         ListNode midNode = findMidNode(head);
  20.         // 右边分区的头结点
  21.         ListNode rightHead = midNode.next;
  22.         // 中断链表，实现真正的分区
  23.         midNode.next = null;
  25.         // 2. 然后递归分区
  26.         ListNode left = insertionSortList(head);
  27.         ListNode right = insertionSortList(rightHead);
  29.         // 3. 合并
  30.         return mergeTwoList(left, right);
  32.     }
  34.     // 找到中间节点
  35.     public ListNode findMidNode(ListNode head) {
  36.         // 使用快慢指针找到中间节点
  37.         if(head == null || head.next == null) {
  38.             return head;
  39.         }
  40.         ListNode slow = head, fast = head.next.next;
  41.         while(fast != null && fast.next != null) {
  42.             slow = slow.next;
  43.             fast = fast.next.next;
  44.         }
  45.         return slow;
  46.     }
  48.     // 合并两个链表
  49.     public ListNode mergeTwoList(ListNode left, ListNode right) {
  50.         // 使用一个虚拟节点 + 头插法，完成两个链表的合并
  51.         ListNode dumyHead = new ListNode(), p = dumyHead;
  52.         while(left != null && right != null) {
  53.             if(left.val <= right.val) {
  54.                 p.next = left;
  55.                 left = left.next;
  56.             } else {
  57.                 p.next = right;
  58.                 right = right.next;
  59.             }
  60.             p = p.next;
  61.         }
  62.         p.next = left == null ? right : left;
  63.         return dumyHead.next;
  64.     }
  65. }

148.排序链表（中等） 链表上的归并排序

  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 sortList(ListNode head) {
  13.         // 归并排序
  14.         if(head == null || head.next == null) {
  15.             return head;
  16.         }
  17.         ListNode midNode = findMidNode(head);
  18.         ListNode rightHead = midNode.next;
  19.         midNode.next = null;
  20.         ListNode left = sortList(head);
  21.         ListNode right = sortList(rightHead);
  22.         return mergeTwoList(left, right);
  23.     }
  25.     public ListNode findMidNode(ListNode head) {
  26.         if(head == null || head.next == null) {
  27.             return head;
  28.         }
  29.         // 快慢指针
  30.         ListNode slow = head, fast = head.next.next;
  31.         while(fast != null && fast.next != null) {
  32.             slow = slow.next;
  33.             fast = fast.next.next;
  34.         }
  35.         return slow;
  36.     }
  38.     public ListNode mergeTwoList(ListNode left, ListNode right) {
  39.         // 虚拟头结点 + 头插法
  40.         ListNode dumyNode = new ListNode(), p = dumyNode;
  41.         while(left != null && right != null) {
  42.             if(left.val <= right.val) {
  43.                 p.next = left;
  44.                 left = left.next;
  45.             } else {
  46.                 p.next = right;
  47.                 right = right.next;
  48.             }
  49.             p = p.next;
  50.         }
  51.         p.next = left == null ? right : left;
  52.         return dumyNode.next;
  53.     }
  54. }

215.数组中的第K个最大元素（中等）

快速排序
  1. class Solution {
  2.     private Random random = new Random();
  4.     public int findKthLargest(int[] nums, int k) {
  5.         // 快排的递归公式：
  6.         // quickSort(s, e) =  partition(s, e) + quickSort(s, q - 1) + quickSort(q + 1, e)
  7.         // q 为 分区点的下标
  8.         return quickSort(nums, 0 , nums.length - 1, k);
  9.     }
  11.     private int quickSort(int[] nums, int s, int e, int k) {
  12.         if(s > e) {
  13.             return - 1;
  14.         }
  15.         // 以[ 大于分区点 | 分区点 | 小于分区点 ] 这种形式进行分区
  16.         int q = randomPartition(nums, s, e);
  17.         // 刚好等于k时，即为
  18.         int size = q-s+1;
  19.         if(size == k) {
  20.             return nums[q];
  21.         } else if (size > k) {
  22.            return quickSort(nums, s, q - 1, k);
  23.         } else {
  24.            return quickSort(nums, q + 1, e, k - size);
  25.         }
  26.     }
  28.     private int randomPartition(int[] nums, int s, int e) {
  29.         // 优化点：随机选择分区点
  30.         int i = random.nextInt(e - s + 1) + s;
  31.         swap(nums, i, e);
  32.         return partition(nums, s, e);
  33.     }
  35.     private int partition(int[] nums, int s, int e) {
  36.         int i = s - 1;
  37.         for(int j = s; j < e; j++) {
  38.             if(nums[j] > nums[e]) {
  39.                 swap(nums, ++i, j);
  40.             }
  41.         }
  42.         swap(nums, ++i, e);
  43.         return i;
  44.     }
  46.     private void swap(int[] nums, int i, int j) {
  47.         int temp = nums[i];
  48.         nums[i] = nums[j];
  49.         nums[j] = temp;
  50.     }
  51. }

面试题17.14.最小K个数（中等）

快速排序
  1. class Solution {
  2.     private Random random = new Random(); 
  4.     public int[] smallestK(int[] arr, int k) {
  5.         quickSort(arr, 0, arr.length - 1, k);
  6.         int[] res = new int[k];
  7.         for(int i = 0; i < res.length; i++) {
  8.             res[i] = arr[i];
  9.         }
  10.         return res;
  11.     }
  13.     private void quickSort(int[] arr, int s, int e, int k) {
  14.         if(s > e) {
  15.             return;
  16.         }
  17.         int p = randomPartition(arr, s, e);
  18.         int num = p - s + 1;
  19.         if(num == k) {
  20.             return;
  21.         } else if(num > k) {
  22.             quickSort(arr, s, p - 1, k);
  23.         } else {
  24.             quickSort(arr, p + 1, e, k - num);
  25.         }
  26.     }
  28.     private int randomPartition(int[] arr, int s, int e) {
  29.         // 优化点
  30.         int i = random.nextInt(e - s + 1) + s;
  31.         swap(arr, i, e);
  32.         return partition(arr, s, e);
  33.     }
  35.     private int partition(int[] arr, int s, int e) {
  36.         int i = s - 1;
  37.         for(int j = s; j < e; j++) {
  38.             if(arr[j] < arr[e]) {
  39.                 swap(arr, ++i, j);
  40.             }
  41.         }
  42.         swap(arr, ++i, e);
  43.         return i;
  44.     }
  46.     private void swap(int[] arr, int i, int j) {
  47.         int temp = arr[i];
  48.         arr[i] = arr[j];
  49.         arr[j] = temp;
  50.     }
  51. }

剑指Offer 51.数组中的逆序对（困难）