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

和力扣 23 合并k个已排序的链表 基本相同

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

import java.util.*;

public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) return null;
        ListNode res = null;
        for (ListNode node : lists) res = mergeTwo(res, node);
        return res;
    }
    
    public ListNode mergeTwo(ListNode node1, ListNode node2) {
        if (node1 == null || node2 == null) return node1 == null ? node2 : node1;
        
        ListNode head = new ListNode(0);
        ListNode tmp = head, tmp1 = node1, tmp2 = node2;
        
        while (tmp1 != null && tmp2 != null) {
            if (tmp1.val <= tmp2.val) {
                tmp.next = tmp1;
                tmp1 = tmp1.next;
            } else {
                tmp.next = tmp2;
                tmp2 = tmp2.next;
            }
            tmp = tmp.next;
        }
        tmp.next = tmp1 == null ? tmp2 : tmp1;
        return head.next;
    }
}