Leetcode21:合并两个有效链表

原题地址：. - 力扣（LeetCode）

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

实现思路

1. 输入检查：首先检查两个链表的头节点。如果一个链表为空，直接返回另一个链表的头节点。
2. 优先队列（最小堆）：使用一个优先队列来存储两个链表中的节点。通过重写比较器，确保队列中的节点按值升序排列。
3. 遍历链表：将两个链表中的所有节点依次加入优先队列。在添加节点后，断开当前节点与后继节点的连接，以避免内存泄漏。
4. 构建合并链表：从优先队列中依次取出节点，构建合并后的链表。使用一个临时节点指针来维护链表的尾部。
5. 返回结果：返回合并后链表的头节点。

源码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 检查链表是否为空
        if (l1 == null) { return l2; } // 如果l1为空，返回l2
        if (l2 == null) { return l1; } // 如果l2为空，返回l1

        // 使用优先队列来存储链表节点
        PriorityQueue<ListNode> node = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val; // 按节点值升序排列
            }
        });

        // 遍历两个链表并将节点加入优先队列
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                node.add(l1); // 添加l1节点
                ListNode next = l1.next; // 记录下一个节点
                l1.next = null; // 断开当前节点与后继的连接
                l1 = next; // 移动到下一个节点
            }
            if (l2 != null) {
                node.add(l2); // 添加l2节点
                ListNode next = l2.next; // 记录下一个节点
                l2.next = null; // 断开当前节点与后继的连接
                l2 = next; // 移动到下一个节点
            }
        }

        // 从优先队列中取出节点构建合并链表
        ListNode result = node.poll(); // 取出第一个节点作为合并链表的头
        ListNode temp = result; // 使用temp指针维护合并链表的尾部
        while (node.peek() != null) {
            ListNode tag = node.poll(); // 取出下一个节点
            temp.next = tag; // 将当前节点链接到合并链表的尾部
            temp = tag; // 更新temp指针
        }
        return result; // 返回合并后的链表头
    }
}

复杂度分析

• 时间复杂度：O((m + n) log(m + n))，其中 m 和 n 分别是两个链表的长度。我们将所有节点加入优先队列的时间复杂度为 O(m + n)，而每次从优先队列中取出节点的时间复杂度为 O(log(m + n))，因此总体复杂度为 O((m + n) log(m + n))。

• 空间复杂度：O(m + n)，我们在优先队列中存储了两个链表的所有节点，因此需要 O(m + n) 的空间。