5.合并K个已排序的链表_合并k个已排序的链表 动态规划

Q：合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
A：分治+递归
1.将两个链表合并（递归）
2.分治：求一个mid，将mid左边的合并，mid右边的合并，最后将两边的合并
3.重复这一过程，直到获取最终的结果

在这里插入代码片import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
        public ListNode mergeKLists(ArrayList<ListNode> lists) {
            return mergeList(lists,0,lists.size()-1);
        }

        public ListNode mergeList(ArrayList<ListNode> lists,int left,int right) {
            if(left==right){
                return lists.get(left);
            }
            if(left>right) {
                return null;
            }
            int mid = left+(right-left)/2;
            return merge(mergeList(lists,left,mid),mergeList(lists,mid+1,right));
        }
        //递归合并两个有序链表
        public ListNode merge(ListNode l1, ListNode l2) {
            if(l1==null) {
                return l2;
            }
            if(l2==null) {
                return l1;
            }
            if(l1.val<l2.val) {
                l1.next=merge(l1.next,l2);
                return l1;
            } else{
                l2.next=merge(l1,l2.next);
                return l2;
            }
        }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45