2019-09-17 合并两个有序链表

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

由于两个链表本身有序，则依次比较两个链表的val值即可，将较小的节点新加入新的链表中，当某一个链表到了尾节点NULL的时候将另一个链表直接附加到新的链表结尾即可。

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* new_l = new ListNode(0); //新建链表
        ListNode* head = new_l; //记录新建链表的头指针，指向链表的头结点
        ListNode* dummy_l1 = l1; //指向l1中每个节点的指针
        ListNode* dummy_l2 = l2; //指向l2中每个节点的指针
        while(dummy_l1!=NULL || dummy_l2!=NULL){
            if(dummy_l1==NULL){
                new_l->next = dummy_l2;
                new_l = dummy_l2;
                return head->next;
            }
            if(dummy_l2==NULL){
                new_l->next = dummy_l1;
                new_l = dummy_l1;
                return head->next;
            }
            ListNode* add_l;
            if(dummy_l1->val>=(dummy_l2->val)){
                add_l = new ListNode(dummy_l2->val);
                dummy_l2 = dummy_l2->next;
            }else{
                add_l = new ListNode(dummy_l1->val);
                dummy_l1 = dummy_l1->next;
            }
            new_l->next = add_l;
            new_l = add_l;
        }
        return head->next;
    }
};