hot100题解 —— 23.合并K个升序链表

一、题目

二、题解

1. 思路

首先，我们之前做过两个升序链表的合并，现在的K个升序链表明显就是再次基础上的演化，那么就可以用分治法把这个问题拆解为多个“两个升序链表合并”的问题

2. 题解

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists == null || lists.length == 0){ return null; } return merge(lists, 0, lists.length - 1); } // 分治法 private ListNode merge(ListNode[] lists, int left, int right){ if(left == right) return lists[left]; int mid = left + (right - left) / 2; ListNode l1 = merge(lists, left, mid); ListNode l2 = merge(lists, mid + 1, right); return merge2List(l1, l2); } // 两个链表的合并 private ListNode merge2List(ListNode l1, ListNode l2){ if(l1 == null) return l2; if(l2 == null) return l1; if(l1.val < l2.val){ l1.next = merge2List(l1.next, l2); return l1; } else { l2.next = merge2List(l1, l2.next); return l2; } } }