Java数据结构算法--合并K个排序链表

合并两个有序链表。

package test;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode Head = new ListNode(0);
        ListNode p = Head;
        while (true) {
            ListNode minNode = null;//必须放在for循环外面
            int minPointer = -1;//minnode和minpointer用的不熟
            for (int i = 0; i < k; i++) {//在三个链表中找第一个最小的节点
                if (lists[i] == null) {//第i个链表为空了，继续
                    continue;//这个continue用的好
                }
                if (minNode == null || lists[i].val < minNode.val) {
                    minNode = lists[i];
                    minPointer = i;//minPointer是只三个链表头部最小的那个
                }
            }
            if (minPointer == -1) {
                break;
            }
            p.next = minNode;
            p = p.next;
            lists[minPointer] = lists[minPointer].next;//是为了从第一个链表的1移动到4，因为1循环下来最小了，所以他的下一个可能也是最小
        }
        return Head.next;
    }
}

public class Main{
    public static void main (String []args){
        ListNode l1 = new ListNode(1);//@466
        ListNode l2 = new ListNode(4);//@467
        ListNode l3 = new ListNode(5);//@468
        ListNode q1 = new ListNode(1);//@469
        ListNode q2 = new ListNode(3);//@470
        ListNode q3 = new ListNode(4);//@471
        ListNode r1 = new ListNode(2);//@472
        ListNode r2 = new ListNode(6);//@473

        ListNode[] l = new ListNode[]{l1, q1, r1};//@474

        l1.next = l2;
        l2.next = l3;
        q1.next = q2;
        q2.next = q3;
        r1.next = r2;

        Solution p = new Solution();
        ListNode b = p.mergeKLists(l);
        while (b != null){
            System.out.print("->"+b.val);
            b = b.next;
        }
    }
}

本文地址：https://blog.csdn.net/qq1922631820/article/details/107994761