21. Merge Two Sorted Lists

21. 合并两个有序链表

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

示例 1：

img

输入：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. 迭代

创建哨兵节点, 然后比较链表的数值, 按照排序顺序链接即可.

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    // sentinel 
    dummy := &ListNode{}
    cur := dummy 
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            cur.Next = list1
            list1 = list1.Next
        } else {
            cur.Next = list2
            list2 = list2.Next
        }

        cur = cur.Next
    }

    if list1 == nil {
        cur.Next = list2
    } else {
        cur.Next = list1
    }

    return dummy.Next
}

2. 递归

由于链表是升序的, 那么对于两个列表的节点, 与后续已经合并的链表关系为:

$\begin{cases} list1[0] + merge(list[1:], list2) & list[0] < list2[0] \\ list2[0] + merge(list1,list2[1:]) & otherwise\end{cases}$

当list1[0] > list2[0], list1[0] 在新链表中较前的位置, 然后其指向剩下节点的合并后节点.

递归出口:

• L1的节点在前, 链接后返回 L1
• L2的节点在前, 链接后返回 L2
• L1为空, 合并后一定是L2的节点, 返回 L2
• L2为空, 合并后一定是L1的节点, 返回 L1

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2 
    } else if list2 == nil {
        return list1
    } else if list1.Val < list2.Val {
        list1.Next = mergeTwoLists(list1.Next, list2)
        return list1
    } else {
        list2.Next = mergeTwoLists(list1, list2.Next)
        return list2
    }
}

Reference

1. https://leetcode.cn/problems/merge-two-sorted-lists/solutions/226408/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/