#leetcode刷題之路21-合併兩個有序鏈表

將兩個有序鏈表合併為一個新的有序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

思路：始終讓l1是頭節點小的那一個，然後拿l2的節點值依次與l1比較並插入l1中。最後返回l1。

#include <iostream>
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<<ans->val<<endl;
        ans=ans->next;
    }
    return 0;
}