1、合并K个升序链表

1.1 题目

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6

示例 2：

输入：lists = [] 输出：[]

示例 3：

输入：lists = [[]] 输出：[]

1.2 思路

分治/归并合并k个排序链表。

  1. 对这k个排序链表组成的数组进行分治划分：从中间划分为左右两部分，左右两部分依次再从中间划分为左右两部分，直到划分到最底层时返回的是单个链表，这时就需要对两个链表进行合并排序，从底向上两两合并；

  2. 对两个排序链表合并成一个链表，并返回链表的头节点：这其实也是一个独立的题目，即合并两个排序链表，有两种方法：

    1. 同时遍历两个链表，依次比较头节点的值，再组装成一个新的链表返回；

    2. 用递归的思想，也是本题用的方法。

      1.3 代码

      1. class Solution {
      2. public ListNode mergeKLists(ListNode[] lists) {
      3.   return merge(lists, 0, lists.length - 1);
      4. }
      6. private ListNode merge(ListNode[] lists, int left, int right) {
      7.   if (left == right) {
      8.       return lists[left];
      9.   }
      10.   if (left > right) {
      11.       return null;
      12.   }
      13.   int mid = (left + right) >> 1;
      14.   return mergeTwoList(merge(lists, left, mid), merge(lists, mid + 1, right));
      15. }
      17. private ListNode mergeTwoList(ListNode head1, ListNode head2) {
      18.   if (head1 == null) {
      19.       return head2;
      20.   }
      21.   if (head2 == null) {
      22.       return head1;
      23.   }
      24.   if (head1.val <= head2.val) {
      25.       head1.next = mergeTwoList(head1.next, head2);
      26.       return head1;
      27.   } else {
      28.       head2.next = mergeTwoList(head1, head2.next);
      29.       return head2;
      30.   }
      31. }
      32. }

      下面这种写法更贴近归并排序的模板：

      1. class Solution {
      2. public ListNode mergeKLists(ListNode[] lists) {
      3.   if (lists == null || lists.length == 0) {
      4.       return null;
      5.   }
      6.   return merge(lists, 0, lists.length - 1);
      7. }
      9. private ListNode merge(ListNode[] lists, int left, int right) {
      10.   if (left < right) {
      11.       int mid = (left +right) >> 1;
      12.       ListNode leftNode = merge(lists, left, mid);
      13.       ListNode rightNode = merge(lists, mid + 1, right);
      14.       return mergeSort(leftNode, rightNode);
      15.   }
      16.   return lists[left];
      17. }
      19. private ListNode mergeSort(ListNode head1, ListNode head2) {
      20.   if (head1 == null) {
      21.       return head2;
      22.   }
      23.   if (head2 == null) {
      24.       return head1;
      25.   }
      26.   if (head1.val < head2.val) {
      27.       head1.next = mergeSort(head1.next, head2);
      28.       return head1;
      29.   } else {
      30.       head2.next = mergeSort(head1, head2.next);
      31.       return head2;
      32.   }
      33. }
      34. }

      2、剑指 Offer 51.数组中的逆序对

      2.1 题目

      在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
      示例 1:

      输入: [7,5,6,4] 输出: 5

2.2 思路

  1. 本体是归并排序的变种，大致流程可以参考归并排序的模板；

  2. 至于何时判断数组中的逆序对，合并阶段本质上是合并两个排序数组的过程，而每当遇到左子数组当前元素 > 右子数组当前元素时，意味着 「左子数组当前元素至末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」。因此，考虑在归并排序的合并阶段统计「逆序对」数量，完成归并排序时，也随之完成所有逆序对的统计。

    2.3 代码

    1. class Solution {
    2.  private int cnt;
    4.  public int reversePairs(int[] nums) {
    5.      merge(nums, 0, nums.length - 1);
    6.      return this.cnt;
    7.  }
    9.  private void merge(int[] nums, int left, int right) {
    10.      int mid = left + ((right - left) >> 1);
    11.      // 当left == right时，数组里只有一个元素，不需要再划分了
    12.      if (left < right) {
    13.          // 划分左子数组
    14.          merge(nums, left, mid);
    15.          // 划分右子数组
    16.          merge(nums, mid + 1, right);
    17.          // 将左右子数组综合排序
    18.          mergeSort(nums, left, right, mid);
    19.      }
    20.  }
    22.  private void mergeSort(int[] nums, int left, int right, int mid) {
    23.      int[] tempArray = new int[right - left + 1];
    24.      int indexTempArray = 0, leftArrayIndex = left, rightArrayIndex = mid + 1;
    26.      while (leftArrayIndex <= mid && rightArrayIndex <= right) {
    27.          if (nums[leftArrayIndex] <= nums[rightArrayIndex]) {
    28.              tempArray[indexTempArray++] = nums[leftArrayIndex++];
    29.          } else {
    30.              // 计算逆序对
    31.              this.cnt += mid - leftArrayIndex + 1;
    32.              tempArray[indexTempArray++] = nums[rightArrayIndex++];
    33.          }
    34.      }
    36.      // 右子数组剩余部分放进tempArray
    37.      while (rightArrayIndex <= right) {
    38.          tempArray[indexTempArray++] = nums[rightArrayIndex++];
    39.      }
    41.      // 左子数组剩余部分放进tempArray
    42.      while (leftArrayIndex <= mid) {
    43.          tempArray[indexTempArray++] = nums[leftArrayIndex++];
    44.      }
    46.      // 将排好序的tempArray替换到原数组nums里对应的起始位置
    47.      for (int k = 0; k < tempArray.length; ++k) {
    48.          nums[left + k] = tempArray[k];
    49.      }
    50.  }
    51. }

    3、148. 排序链表

    这个题好呀。

    3.1 题目

    给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

    3.2 思路

    整体思路还是用分治的思想，先分（划分排序链表），再治（合并两个排序链表），这题用到了三个题目：

  3. 划分排序链表，注意返回条件（链表为null或者链表仅有一个元素，就返回）；

  4. 取链表中间的节点，这里是快慢指针求链表中点的题目，注意链表跟数组还不完全一样，找到链表中点后，要把对应的尾节点置为null；

  5. 合并两个排序链表的题目，可以递归或者依次遍历。

    3.3 代码

    1. class Solution {
    2.  public ListNode sortList(ListNode head) {
    3.      if (head == null || head.next == null) {
    4.          return head;
    5.      }
    7.      ListNode mid = getMid(head);
    8.      ListNode tmp = mid.next;
    9.      mid.next = null;
    10.      return mergeTwo(sortList(head), sortList(tmp));
    11.  }
    13.  private ListNode getMid(ListNode head) {
    14.      ListNode fast = head, slow = head;
    15.      while (fast.next != null && fast.next.next != null) {
    16.          fast = fast.next.next;
    17.          slow = slow.next;
    18.      }
    19.      return slow;
    20.  }
    22.  private ListNode mergeTwo(ListNode head1, ListNode head2) {
    23.      if (head1 == null) {
    24.          return head2;
    25.      }
    26.      if (head2 == null) {
    27.          return head1;
    28.      }
    29.      if (head1.val < head2.val) {
    30.          head1.next = mergeTwo(head1.next, head2);
    31.          return head1;
    32.      } else {
    33.          head2.next = mergeTwo(head1, head2.next);
    34.          return head2;
    35.      }
    36.  }
    37. }