合并两个已排序的链表是一个基础操作。其核心思想是维护一个新的链表，不断地从两个输入链表中取出值较小的节点添加到新链表末尾，直至其中一个链表为空，然后将另一个链表的剩余部分直接接在新链表之后。

合并两个链表的实现

public ListNode mergeTwoSortedLists(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }

    ListNode dummyHead = new ListNode(0); // 哨兵节点，简化头节点处理
    ListNode current = dummyHead;

    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            current.next = new ListNode(list1.val); // 创建新节点，避免直接引用原节点
            list1 = list1.next;
        } else {
            current.next = new ListNode(list2.val);
            list2 = list2.next;
        }
        current = current.next;
    }

    // 将剩余未合并的节点连接到末尾
    if (list1 != null) {
        current.next = list1;
    } else {
        current.next = list2;
    }

    return dummyHead.next;
}

对于合并 K 个升序链表的问题，有多种有效的方法。

顺序合并策略 最直观的策略是将 K 个链表两两配对进行合并。可以从第一个链表开始，依次与后续的链表进行合并。每次合并的结果都成为下一次合并的输入。

顺序合并 K 个链表的实现

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        ListNode mergedList = null;
        for (ListNode list : lists) {
            mergedList = mergeTwoSortedLists(mergedList, list);
        }
        return mergedList;
    }

    // mergeTwoSortedLists 方法同上
    private ListNode mergeTwoSortedLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                current.next = new ListNode(list2.val);
                list2 = list2.next;
            }
            current = current.next;
        }
        if (list1 != null) current.next = list1;
        else current.next = list2;
        return dummyHead.next;
    }
}

分治合并策略 分治思想在此问题中同样适用。可以将 K 个链表看作一个数组，递归地将数组分成两半，分别合并左右两半的链表，最后再将合并后的两个链表进行合并。这种方式可以更均衡地分配合并任务，潜在地提高效率。

分治合并 K 个链表的实现

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return divideAndConquerMerge(lists, 0, lists.length - 1);
    }

    private ListNode divideAndConquerMerge(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        // 处理当 start > end 的情况，例如 lists.length = 0 时
        if (start > end) {
            return null;
        }
        
        int mid = start + ((end - start) >> 1); // 计算中间索引
        ListNode leftMerged = divideAndConquerMerge(lists, start, mid);
        ListNode rightMerged = divideAndConquerMerge(lists, mid + 1, end);
        
        return mergeTwoSortedLists(leftMerged, rightMerged);
    }

    // mergeTwoSortedLists 方法同上
    private ListNode mergeTwoSortedLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                current.next = new ListNode(list2.val);
                list2 = list2.next;
            }
            current = current.next;
        }
        if (list1 != null) current.next = list1;
        else current.next = list2;
        return dummyHead.next;
    }
}

优先队列合并策略 另一种高效的方法是利用优先队列（最小堆）。将 K 个链表的头节点（或者所有节点）的数值放入优先队列。每次从优先队列中取出最小值，构成新链表的一个节点。如果取出的节点来自某个链表，则将其下一个节点也加入优先队列。

优先队列合并 K 个链表的实现

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        // 优先队列存储链表节点，根据 val 排序
        Queue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

        // 将所有链表的第一个节点加入优先队列
        for (ListNode head : lists) {
            if (head != null) {
                minHeap.offer(head);
            }
        }

        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;

        while (!minHeap.isEmpty()) {
            ListNode smallestNode = minHeap.poll(); // 取出当前最小值的节点
            current.next = new ListNode(smallestNode.val); // 添加到结果链表
            current = current.next;

            // 如果被取出的节点还有下一个节点，则将其加入优先队列
            if (smallestNode.next != null) {
                minHeap.offer(smallestNode.next);
            }
        }

        return dummyHead.next;
    }
}

// ListNode 定义
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}