题解 | 合并k个已排序的链表

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        if(lists == null||lists.size()== 0){
            return null;
        }
        ListNode result = split(lists,0,lists.size()-1);
        return result;
    }

    private ListNode split(ArrayList<ListNode> lists, int left, int right) {
        if(left == right) return lists.get(left);
        int mid = left + (right-left)/2;
        ListNode l = split(lists,left,mid);
        ListNode r = split(lists,mid+1,right);
        return merge(l,r);
    }

    private ListNode merge(ListNode pHead1, ListNode pHead2) {
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        if(pHead1 == null){
            return pHead2;
        }else if(pHead2 == null){
            return pHead1;
        }
        else{
            while(pHead1!=null&&pHead2!=null){
                if(pHead1.val<pHead2.val){
                    tail.next = pHead1;
                    pHead1 = pHead1.next;
                }else{
                    tail.next = pHead2;
                    pHead2 = pHead2.next;
                }
                tail = tail.next;
            }
            if(pHead1 == null){
                tail.next = pHead2;
            }else{
                tail.next = pHead1;
            }
        }
        return dummy.next;
    }
}

使用的是分治思想来简化合并的步骤 （分治我最开始是在数组排序的时候学到的） 知道了分治之后就正常合并链表就好了 不是非常难 这里简述一下合并链表的流程 先判断两个链表是不是为空 然后 创建一个头指针 然后使用双指针进行比较 选出较小的那个节点然后把那个节点变成下一个节点 然后进行节点的移动 最后就是当一个链表的节点弄完之后 将另外一个链表的剩余部分赋值给当前节点的next就行