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; } } }