LeetCode题解-链表标签：合并两个有序链表

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

示例：

输入：

graph LR
A[1]-->B[2]
B[2]-->C[4]

graph LR
A[1]-->B[3]
B[3]-->C[4]

输出：

graph LR
A[1]-->B[1]
B[1]-->C[2]
C[2]-->D[3]
D[3]-->E[4]
E[4]-->F[4]

思路：

已知条件：两个链表的头节点l1和l2。

对于两个升序链表，它们的长度不一定相等，当我们把较短的链表合并完成后，直接连接较长链表的剩余部分即可。

我们并不知道哪一个的头节点值更小，所以需要分类讨论。

递归法：

我们可以用如下的公式定义我们的递归merge操作：

判断l1和l2哪一个链表的头节点值较小，将较小的那个节点的下一个节点与另一个链表进行递归merge。

递归的出口：如果递归到l1[0]或l2[0]为null时，直接返回另外一个链表。另外一个链表可能也为null（如果原链表长度相等），或者非null（原链表长度不等）。

单链表节点类定义可查看文章：数据结构之链表-基础知识

Java语言实现如下：

public static SinglyLinkedListNode mergeTwoSortedLinkedListRecursionImpl(SinglyLinkedListNode l1,
                                                                         SinglyLinkedListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoSortedLinkedListRecursionImpl(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoSortedLinkedListRecursionImpl(l1,l2.next);
        return l2;
    }
}

迭代法：

正所谓所有的递归都可以转化成迭代。

由于待合并的两个链表都有序，合并后的头节点要么是l1要么是l2。如果我们不希望修改原来的链表，就需要构造出一个新链表，顺序连接两个原链表的各个节点。

首先，我们创建一个哨兵节点hair，然后维护一个cur指针，每次使用cur指针去连接各个节点。我们依次比较l1和l2节点的值，如果l1的值小于l2，则用cur连接l1，然后l1右移；否则，用cur连接l2，然后l2右移。直到l1或者l2为null，将另一个节点的剩余节点连接至cur，然后再返回hair.next，即为合并后链表的新头节点。

哨兵节点hair：指针域next指向的节点即为合并后的链表的头节点。

Java语言实现如下：

public static SinglyLinkedListNode mergeTwoSortedLinkedList(SinglyLinkedListNode l1,
                                                            SinglyLinkedListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    SinglyLinkedListNode hair = new SinglyLinkedListNode();
    SinglyLinkedListNode cur = hair;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    if (l1 == null) cur.next = l2;
    if (l2 == null) cur.next = l1;
    return hair.next;
}