LeetCode 21 合并两个有序链表

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

示例 1：

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

方法：迭代
新链表的头结点不确定时，创建虚拟头结点。

C++ ：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1), prehead = dummy ;
        while( l1 && l2) {
            if (l1->val < l2->val) {
                prehead = prehead->next = l1;
                l1 = l1->next;
            }
            else {
                prehead = prehead->next = l2;
                l2 = l2->next ;
            }
        } 
        if( l1) prehead->next = l1 ;
        if( l2) prehead->next = l2 ;
        return dummy->next ;
    }
};

方法2： 递归
不创建新的链表，在原链表上操作
C++：

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

Golang：

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