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

示例：

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

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

 

思路：始终让l1是头节点小的那一个，然后拿l2的节点值依次与l1比较并插入l1中。最后返回l1。

#include 
     
      using namespace std;struct ListNode {        int val;         ListNode *next;        ListNode(int x) : val(x), next(NULL) {}    };ListNode* createlist(int n)//有头节点的{    ListNode *head = (ListNode*)malloc(sizeof(ListNode));    ListNode *pre = head;    for (int i = 0; i < n; i++)    {        ListNode *p = (ListNode*)malloc(sizeof(ListNode));        cin >> p->val;        pre->next = p;        pre = p;    }    pre->next = nullptr;    return head;}ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {    ListNode*temp;    ListNode*t;    if(l1== nullptr) return l2;    if(l2== nullptr) return l1;    if(l1->val>l2->val)//把头节点值小的放前面    {        t=l1;l1=l2;l2=t;    }    ListNode*head=l1;    while(l2!= nullptr)    {        if(l1->next== nullptr)        {            l1->next=l2;            return head;        }        else if(l1->val<=l2->val&&l1->next->val>=l2->val)        {            temp=l2->next;            t=l1->next;            l1->next=l2;            l2->next=t;            l1=l2;            l2=temp;        }        else l1=l1->next;    }    return head;}int main() {    ListNode* l1=createlist(3);    ListNode* l2=createlist(3);    ListNode *ans=mergeTwoLists(l1->next,l2->next);    //ans=ans->next->next;    while(ans!= nullptr)    {        cout<
      
       val<
       
        next;    }    return 0;}