合并k个已排序的链表

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    public ListNode mergeKLists(ArrayList<ListNode> lists){
        if(lists.isEmpty()){
            return null;
        }
        ListNode list=lists.get(0);
        for(int i=1;i<lists.size();i++){
            ListNode list2=lists.get(i);
            list=mergeKLists(list,list2);
        }
        return list;
    }
    public ListNode mergeKLists (ListNode pHead1, ListNode pHead2) {

        ListNode pHead = new ListNode(0);
        ListNode temp1 = pHead;
        while (pHead1 != null && pHead2 != null) {

            if (pHead1.val <= pHead2.val) {
                temp1.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                temp1.next = pHead2;
                pHead2 = pHead2.next;
            }
            temp1 = temp1.next;
        }
        if (pHead1 != null) {
            temp1.next = pHead1;
        }
        if (pHead2 != null) {
            temp1.next = pHead2;
        }
        return pHead.next;
    }
}

归并排序的思想，两两合并，重复直至只剩一个

import java.util.*;

// 类似归并排序：两两合并
public class Solution {
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        while (lists.size() > 1) { // 合并至只剩1个
            ArrayList<ListNode> newLists = new ArrayList<>(); // 新List
            for (int i = 0; i < lists.size(); i += 2) { // 选两两合并
                ListNode node1 = lists.get(i), node2 = null;
                if (i + 1 < lists.size()) node2 = lists.get(i + 1);
                newLists.add(merge(node1, node2));
            }
            lists = newLists;
        }
        return lists.size() == 0 ? null : lists.get(0);
    }

    // 合并两个升序链表
    private ListNode merge(ListNode node1, ListNode node2) {
        if (node1 == null) return node2;
        if (node2 == null) return node1;

        ListNode head = new ListNode(-1), p = head; // 表头节点
        while (node1 != null && node2 != null) { // 合并
            if (node1.val <= node2.val) {
                p.next = node1;
                node1 = node1.next;
            } else {
                p.next = node2;
                node2 = node2.next;
            }
            p = p.next;
        }
        while (node1 != null) { // 剩余节点
            p.next = node1;
            node1 = node1.next;
            p = p.next;
        }
        while (node2 != null) { // 剩余节点
            p.next = node2;
            node2 = node2.next;
            p = p.next;
        }
        return head.next;
    }
}

import java.util.*;

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

/**
 * NC51 合并k个已排序的链表
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // return solution1(lists);
        // return solution2(lists);
        return solution22(lists);
        // return solution3(lists);
    }

    /**
     * 连续归并
     * @param lists
     * @return
     */
    private ListNode solution1(ArrayList<ListNode> lists){
        ListNode dummyHead = new ListNode(-1);
        for(ListNode list: lists){
            dummyHead.next = merge(dummyHead.next, list);
        }

        return dummyHead.next;
    }

    /**
     * 合并
     * 合并两个有序链表
     * @param list1
     * @param list2
     * @return
     */
    private ListNode merge(ListNode list1, ListNode list2){
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }

        if(list1.val <= list2.val){
            list1.next = merge(list1.next, list2);
            return list1;
        }else{
            list2.next = merge(list1, list2.next);
            return list2;
        }
    }

    /**
     * 二分归并
     * @param lists
     * @return
     */
    private ListNode solution2(ArrayList<ListNode> lists){
        int k = lists.size();
        if(k == 0){
            return null;
        }

        int left,right;
        for(int gap=k; gap>1; gap=(gap+1)/2){
            for(int i=0; i<(gap+1)/2; i++){
                left = i;
                right = gap-i-1;
                if(left < right){
                    lists.set(left, merge(lists.get(left), lists.get(right)));
                    lists.remove(right);
                }
            }
        }

        return lists.get(0);
    }

    /**
     * 递归归并
     * @param lists
     * @return
     */
    private ListNode solution22(ArrayList<ListNode> lists){
        return divide(lists, 0, lists.size()-1);
    }

    /**
     * 分治: 递归
     * @param lists
     * @param left
     * @param right
     * @return
     */
    private ListNode divide(ArrayList<ListNode> lists, int left, int right){
        if(left > right){
            return null;
        }
        else if(left == right){
            return lists.get(left);
        }

        int mid = left+(right-left)/2;

        return merge(divide(lists, left, mid), divide(lists, mid+1, right));
    }

    /**
     * 堆: 优先队列
     * @param lists
     * @return
     */
    private ListNode solution3(ArrayList<ListNode> lists){
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(ListNode node: lists){
            while(node != null){
                minHeap.offer(node.val);
                node = node.next;
            }
        }

        ListNode head = new ListNode(-1);
        ListNode tail = head;
        while(!minHeap.isEmpty()){
            tail.next = new ListNode(minHeap.poll());
            tail = tail.next;
        }

        return head.next;
    }
}

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Solution2 {

/*

todo:  不需要头节点.

 */

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge(ListNode pHead1, ListNode pHead2) {
//      总和节点
        ListNode all = new ListNode(0, null);
        ListNode all_index = all;
//        两个指针都有值，且值不相等，比较两个值，较小的那个节点作为新链表的节点，然后指针向后移动一位
        ListNode one_index = pHead1;
        ListNode two_index = pHead2;
        ListNode temp1 = null;
        ListNode temp = null;

//        链表的到达末尾,的标志是next为null.
        while (one_index != null && two_index != null) {
            if (one_index.val < two_index.val) {
                temp = one_index;
                one_index = one_index.next;

                all_index.next = temp;

                all_index = all_index.next;
            } else {
                temp1 = two_index;
                two_index = two_index.next;
                all_index.next = temp1;
                all_index = all_index.next;
            }
        }
        if (one_index == null) {
            all_index.next = two_index;
        } else {
            all_index.next = one_index;
        }

        return all.next;
    }


    // write code here
    @Test
    public void test1() {
        Integer[] ListNodevals = {1};
        Integer[] ListNodevals1 = {2};

        ListNode listNode1 = headList(ListNodevals);
        ListNode listNode2 = headList(ListNodevals1);

//        获得头和尾部分.
        ListNode listNode = Merge(listNode1, listNode2);
//        打印
        while (listNode != null) {
            System.out.println("listNode.val:" + listNode.val);
            listNode = listNode.next;
        }

    }

    public ListNode headList(Integer[] ListNodevals) {
        //头结点
        ListNode head = new ListNode();
        ////指针.
        ListNode ListNode = head;

        for (int i = 0; i < ListNodevals.length; i++) {
            //            新的节点
            ListNode new_ListNode = new ListNode(ListNodevals[i], null);
            //             链表指针的next指向新的节点
            ListNode.next = new_ListNode;
            ListNode = new_ListNode;
        }
//        没有头结点.
        return head.next;
    }

    /**
     * 找到最小value变成加入到总链表或者其他结构
     * 之后变动的链表1进行++
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists.size() == 0 || lists == null) {
            return null;
        }
//        每个链表有链表指针和temp;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (ListNode list : lists) {
            while (list != null) {
                pq.add(list.val);

                list = list.next;
            }
        }

        ListNode head_node = new ListNode(0, null);
        ListNode head = head_node;
        ListNode temp = head;

        while (!pq.isEmpty()) {
            ListNode listNode1 = new ListNode(pq.poll(), null);
            temp.next = listNode1;
            temp = temp.next;
        }
        return head.next;
    }

    @Test
    public void test2() {

        Integer[] ListNodevals = {1, 2, 3};
        Integer[] ListNodevals1 = {4,5,6,7};

        ListNode listNode = headList(ListNodevals);
        ListNode listNode1 = headList(ListNodevals1);

        ArrayList<ListNode> lists = new ArrayList<>();
        lists.add(listNode);
        lists.add(listNode1);

        ListNode all_list = mergeKLists(lists);
        while (all_list != null) {
            System.out.println("all_list.val:" + all_list.val);
            all_list = all_list.next;
        }

    }
}

 

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {

        // write code here
        List<Integer> vals = new ArrayList<>();

        for(ListNode head : lists){
            while(head!=null){
                vals.add(head.val);
                head = head.next;
            }
        }

        Collections.sort(vals);

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        for(Integer n : vals){
            cur.next =  new ListNode(n);
            cur=cur.next;
        }
        
        return dummy.next;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        if(lists.isEmpty()){
            return null;
        }
        ListNode list = lists.get(0);
        // write code here
        for (int i = 1; i < lists.size(); i++) {
            ListNode list2 = lists.get(i);
            list = Marg(list,list2);
        }
        return list;
    }

    public static ListNode Marg(ListNode node1, ListNode node2) {
        if (node1 == null) {
            return node2;
        }

        if (node2 == null) {
            return node1;
        }

        if (node1.val <= node2.val) {
            node1.next = Marg(node1.next, node2);
            return node1;
        }else{
            node2.next = Marg(node2.next, node1);
            return node2;
        }

    }
}

public ListNode mergeKLists (ArrayList<ListNode> lists) {
        if(lists.size() == 0){
            return null;
        }
        if(lists.size() == 1){
            return lists.get(0);
        }
        ListNode const_head = new ListNode(0);
        ListNode pre = const_head;
        while(lists.size() > 1){
            ListNode min_node = lists.get(lists.size()-1);
            int min_index  = lists.size()-1;
            for(int i=lists.size()-1;i>=0;i--){
                ListNode cur_node = lists.get(i);
                if(cur_node == null){
                    lists.remove(i);
                    min_index--;
                }else if(min_node == null || cur_node.val < min_node.val){
                    min_node = cur_node;
                    min_index = i;
                }
            }
            if(min_node == null) return const_head.next;;
            pre.next = min_node;
            pre = pre.next;
            lists.set(min_index,min_node.next);
        }
        pre.next = lists.get(0);
        return const_head.next;
    }

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here

        // 算法时间复杂度O(NlogN)，额外空间复杂度O(logN)

        // 分治思想，参考归并排序，K个链表可以两两合并，新合并的链表再两两合并，直到K个链表全部合并
        // 这道题的重点就是把lists的划分合并区间函数的递归调用写出来
        return divideMerge(lists, 0, lists.size() - 1);
    }

    // 划分合并区间函数
    ListNode divideMerge(ArrayList<ListNode> lists, int left, int right) {
        // 递归出口 - 划分到没法再分为止
        if (left > right) {
            return null;
        }
        else if (left == right) {
            return lists.get(left);
        }

        // 重点！从中间分成两段，再将合并好的两段合并
        int mid = (left + right) / 2;
        return Merge(
            divideMerge(lists, left, mid), 
            divideMerge(lists, mid + 1, right)
            );
    }

    // 两个链表合并函数 - 上一道题的过程
    public ListNode Merge(ListNode pHead1, ListNode pHead2) {
        // 算法时间复杂度O(N)，额外空间复杂度O(1)

        // 1.处理边界情况，确保两个链表非空
        if (pHead1 == null) {
            return pHead2;
        }
        if (pHead2 == null) {
            return pHead1;
        }

        // 2.找到两个有序链表头结点中较小的那个，记为targetHead，以target链表为合并的容器，另外一个链表记为source链表
        ListNode targetHead;
        ListNode sourceHead;
        if (pHead1.val <= pHead2.val) {
            targetHead = pHead1;
            sourceHead = pHead2;
        } else {
            targetHead = pHead2;
            sourceHead = pHead1;
        }

        // 3.遍历target链表，针对每个targetCur结点，去source中尝试找到这样一个子序列：
        //      该子序列的所有结点满足 >= targetCur 且 < targetNext(targetCur.next)
        // 若能够找到，则用sourceStart和sourceEnd固定其头和尾的位置，然后将这个子序列完整纳入到target链表中
        ListNode targetCur = targetHead;
        ListNode targetNext = targetHead.next;
        ListNode sourceCur = sourceHead;
        ListNode sourceStart = null;
        ListNode sourceEnd = null;
        while (targetCur != null) {
            System.out.println("targetCur: " + targetCur.val);
            targetNext = targetCur.next;
            if (sourceCur != null && sourceCur.val >= targetCur.val) {
                // 3.1 发现了source链表中有一个 >= targetCur的结点，先记为sourceStart
                // 注意！sourceStart可能已经 >= targetNext的，这种情况是不能将其纳入的，后续要对这种情况做好判断！
                sourceStart = sourceCur;
                System.out.println("发现了一个source链表中比targetCur大的结点：" +
                                   sourceStart.val);
                if (targetNext == null) {
                    // 3.2 如果targetCur没有下一个结点，那么sourceStart及其后续结点必然满足要求
                    // 此时就会把从sourceStart开始剩余的source结点全部纳入进来，可以直接结束
                    System.out.println("此时target链表已经到了最后一个结点了");
                    targetCur.next = sourceStart;
                    break;
                }

                // 3.3 如果targetCur还有下一个结点，那么必须找到 >= targetCur，且 < targetNext的source结点
                while (sourceCur.next != null && sourceCur.next.val < targetNext.val) {
                    // 找到source链表中一系列比targetCur大，且比targetNext小的source结点，确定它们的头和尾
                    // 注意！sourceCur可能本身已经 >= targetNext了，结束while循环后一定要做对应判断！
                    sourceCur = sourceCur.next;
                }
                sourceEnd = sourceCur;
                // 3.4 此时存在一种可能，即只有唯一的sourceCur，确实 >= target，但是它同时 >= targetNext，此时不应该纳入，应该提前迭代
                if (sourceEnd.val >= targetNext.val) {
                    System.out.println("虽然 >= targetCur，但它同时 >= targetNext，此时也不应该放入");
                    targetCur = targetNext;
                    continue;
                }
                sourceCur = sourceCur.next;
                // 3.5 找到了sourcr链表中满足条件的子序列，且以sourceStart开头，sourceEnd结尾，将他们整体纳入到target链表中
                targetCur.next = sourceStart;
                sourceEnd.next = targetNext;
            }
            // 3.6 target迭代遍历
            targetCur = targetNext;
        }
        return targetHead;
    }
}

public ListNode mergeKLists (ArrayList<ListNode> lists) {
    // write code here
    if (lists == null || lists.isEmpty()) return null;

    Iterator<ListNode> it = lists.iterator();
    ListNode res = it.next();
    while (it.hasNext()) res = merge(res, it.next());

    return res;
}

private ListNode merge(ListNode a, ListNode b) {
    if (a == null) return b; 
    if (b == null) return a; 

    if(a.val <= b.val) {
        a.next = merge(a.next, b);
        return a;
    } else {
        b.next = merge(b.next, a);
        return b;
    }
}

多链表合并
import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        ListNode head=new ListNode(0), cur=head, min=head;
        int minIdx=0;
        while(true){
            min=null;
            for(int i=0;i<lists.size();++i){
                if(lists.get(i)!=null){
                    if(min==null){
                        min=lists.get(i);
                        minIdx=i;
                    }else if(min.val>lists.get(i).val){
                        min=lists.get(i);
                        minIdx=i;
                    }
                }
            }
            if(min==null)
                break;
            cur.next=min;
            cur=min;
            lists.set(minIdx, min.next);
        }
        return head.next;
    }
}

    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((x1, x2) -> x1.val - x2.val);
        // pq.addAll(lists.stream().filter(x -> x != null).toList());
        for (ListNode head : lists) {
            if (head != null) {
                pq.add(head);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode p = dummy;

        while (pq.size() > 0) {
            ListNode top = pq.poll();
            p.next = top;
            top = top.next;
            p = p.next;
            if (top != null) {
                pq.add(top);
            }
        }
        return dummy.next;
    }

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        if(lists.size()==0||lists == null) return null;
        ListNode head = lists.get(0);
        for(int i = 1;i<lists.size();i++) {
            head = getNode(head,lists.get(i));
        }
        return head;
    }
    public ListNode getNode(ListNode pHead1,ListNode pHead2) {
        if(pHead1==null) return pHead2;
        if(pHead2==null) return pHead1;
        ListNode sentinel = new ListNode(-1);
        ListNode cur = sentinel;
        while(pHead1!=null&&pHead2!=null) {
            if(pHead1.val > pHead2.val) {
                cur.next = pHead2;
                pHead2 = pHead2.next;
            }else{
                cur.next = pHead1;
                pHead1 = pHead1.next;
            }
            cur = cur.next;
        }
        if(pHead1==null) cur.next = pHead2;
        else cur.next = pHead1;
        return sentinel.next;
    }
}