21 合并两个有序链表

一、题目

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

二、题解

思路： 用递归合并。

• 递归边界：任一链表为空时，直接返回另一个链表。
• 比较两个链表当前头节点的值，谁小谁作为合并后的头节点，并让它的 next 指向「剩余部分与另一链表」递归合并的结果。

/**
 * 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 list1, ListNode list2) {
        // 【递归边界】如果其中一个链表为空，说明另一个链表剩下的部分就是排好序的，直接返回即可
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }

        // 【核心逻辑：谁小谁当头】
        // 比较当前两个链表的头节点的值
        else if (list1.val < list2.val) {
            // 如果 list1 的节点更小，那么它应该排在前面。
            // 它的下一个节点指向哪里？指向“list1 剩下的部分”和“整个 list2”合并后的结果。
            list1.next = mergeTwoLists(list1.next, list2);
            // 本层递归完成，向上级返回确定好的当前较小节点
            return list1;
        } else {
            // 反之，如果 list2 的节点更小（或相等），list2 排在前面。
            // 它的下一个节点指向“整个 list1”和“list2 剩下的部分”合并后的结果。
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

时间复杂度：$O(n + m)$

空间复杂度：$O(n + m)$