L21 合并两个有序链表

链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解：
新建一个链表，比较两个链表中元素的值，把比较小的那个，加入到新链表中，两个链表的长度可能不同。所以最终会有一个链表先完成插入所有的元素。则直接两一个未完成的链表及直接链入新链表的末尾。

递归的方法：当某个链表为空了就返回另一个。

// 递归
    ListNode* mergeTwoLists(ListNode* head1, ListNode* head2) {
        if(!head1) return head2;
        if(!head2) return head1;
        if(head1->val < head2->val){
            head1->next = mergeTwoLists(head1->next,head2);
            return head1;
        }
        else{
            head2->next = mergeTwoLists(head2->next,head1);
            return head2;
        }
    }
    //迭代
    ListNode* mergeTwoLists(ListNode* head1, ListNode* head2) {
        if(head1 ==NULL) return head2;
        if(head2 ==NULL) return head1;
        ListNode *newhead = new ListNode(-1),*cur=newhead;
        while(head1&&head2){
            if(head1->val < head2->val){
                cur->next = head1;
                head1=head1->next;
            }
            else{
                cur->next = head2;
                head2=head2->next;
            }
            cur = cur->next;
        }
        cur->next = head1?head1:head2;
        return newhead->next;
    }