Leetcode:mergeTwoLists合并两个有序链表

题目：

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

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

思路：

暴力解法 ListNode一个新指针L 用一个while循环（当l1和l2都不为空的时候） L指向l1->value和l2->value小的那个 最后跳出循环后 再把指针指向还没循环完的链表。

递归解法：

代码：

（暴力）

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        ListNode* List = new ListNode(0);
        ListNode* temp = List;
        if(list1 == NULL)return list2;
        if(list2 == NULL)return list1;
        ListNode* p1 = list1;
        ListNode* p2 = list2;
        while(p1 != NULL && p2 != NULL)
        {
            if(p1->val <= p2->val)
            {
                temp->next = p1;
                p1 = p1->next;
            }
            else
            {
                temp->next = p2;
                p2 = p2->next;
            }
            temp = temp->next;
        }
        temp->next = p1 == NULL? p2 : p1;
        return List->next;
    }
};

（递归）

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

        ListNode* l1 = list1;
        ListNode* l2 = list2;
        if(l1 == NULL)return l2;
        if(l2 == NULL)return l1;
        if(l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next,l2);
             return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};