LeetCode 21 合并两个有序链表
1.题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
2.题解：
方法：迭代
新链表的头结点不确定时，创建虚拟头结点。
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
}
}