题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

算法一

现将两张链表拼接在一起，然后遍历链表，交换数据

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        auto l=l1;
        if(!l1)return l2;
        ListNode* pre;
        while(true){
           if(l->next==NULL){
               l->next=l2;
               break;
           }
           l=l->next;
        }

        for(auto i=l1;i;i=i->next)pre=i;

        for(auto i=l1;i!=pre;i=i->next){
            for(auto j=l1;j!=pre;j=j->next){
                if(j->val>j->next->val){
                    int temp=j->val;
                    j->val=j->next->val;
                    j->next->val=temp;
                }
            }
        }

        return l1;
    }
};

算法二

看的学长的解法，通过创建第三链表，谁小就链接谁，一定不要忘记更新第三链表的cur

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {

        if(!l1)return l2;
        if(!l2)return l1;

        auto a=l1,b=l2;
        ListNode* p=new ListNode(0);
        ListNode* cur=p;

        while(a&&b){
            if(a->val<=b->val){
                cur->next=a;
                cur->next->val=a->val;
                a=a->next;
                cur=cur->next;
            }else{
                cur->next=b;
                cur->next->val=b->val;
                b=b->next;
                cur=cur->next;
            }
        }

        if(!a)cur->next=b;
        else cur->next=a;

        return p->next;
    }
};

算法三

是将算法二中在将两张链表链接到第三链表时，不需要赋值，直接记录指针即可

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {

        if(!l1)return l2;
        if(!l2)return l1;

        auto a=l1,b=l2;
        ListNode* p=new ListNode(0);
        ListNode* cur=p;

        while(a&&b){
            if(a->val<=b->val){
                cur->next=a;
                a=a->next;
                cur=cur->next;
            }else{
                cur->next=b;
                b=b->next;
                cur=cur->next;
            }
        }

        if(!a)cur->next=b;
        else cur->next=a;

        return p->next;
    }
};