题目

image.png

思路

  • 合并链表，需要一个合并方法，由因为是两两合并，因此可以通过分治法将链表拆分成两个为一组的形式

    代码

    1.   public ListNode mergeKLists(ListNode[] lists) {
    2.       int len = lists.length;
    3.       if (len == 0) return null;
    4.       if (len == 1) return lists[0];
    5.       return recur(lists, 0, len - 1);
    6.   }
    8.   public ListNode recur(ListNode[] lists, int left, int right) {
    9.       if (left == right) return lists[left];
    10.       if (right - left + 1 == 2) return merge(lists[left], lists[right]);
    11.       ListNode l = recur(lists, left, (left + right) / 2);
    12.       ListNode r = recur(lists, (left + right) / 2 + 1, right);
    13.       return merge(l, r);
    14.   }
    16.   public ListNode merge(ListNode p1, ListNode p2) {
    17.       ListNode dummy = new ListNode(0);
    18.       ListNode cur = dummy;
    19.       while (p1 != null && p2 != null) {
    20.           if (p1.val > p2.val) {
    21.               cur.next = p2;
    22.               p2 = p2.next;
    23.           } else {
    24.               cur.next = p1;
    25.               p1 = p1.next;
    26.           }
    27.           cur = cur.next;
    28.       }
    29.       ListNode p = p1 == null ? p2 : p1;
    30.       cur.next = p;
    31.       return dummy.next;
    32.   }

    合并K个升序链表