力扣21. 合并两个有序链表

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

示例：

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

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

错误思路

本着我不能多敲的原则，在这里写一下我错误的思路

首先在两链表其中一个不为空的情况下取值，然后如果只有一个取一个的值插入链表，两个元素同时存在的情况下比较两个元素，按大小依次插入链表

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *head;
    struct ListNode *l3=(struct ListNode*)malloc(sizeof(struct ListNode));
    l3->val=0;
    l3->next=NULL;
    head=l3;
    while((l1!=NULL)||(l2!=NULL)){
        if(l1==NULL){
            l3->val=l2->val;
            if(l2->next!=NULL){
                struct ListNode *l4=(struct ListNode*)malloc(sizeof(struct ListNode));
                l4->val=0;
                l4->next=NULL;
                l3->next=l4;
                l3=l4;
                l2=l2->next;
            }
            else{
                l2=l2->next;
            }
        }
        else if(l2==NULL){
            l3->val=l1->val;
            if(l1->next!=NULL){
                struct ListNode *l4=(struct ListNode*)malloc(sizeof(struct ListNode));
                l4->val=0;
                l4->next=NULL;
                l3->next=l4;
                l3=l4;
                l1=l1->next;
            }
            else{
                l1=l1->next;
            }
        }
        else{
            if(l1->val<l2->val){
                l3->val=l1->val;
                struct ListNode *l4=(struct ListNode*)malloc(sizeof(struct ListNode));
                l4->val=l2->val;
                l3->next=l4;
                l3=l4;
                if((l1->next!=NULL)||(l2->next!=NULL)){
                    struct ListNode *l5=(struct ListNode*)malloc(sizeof(struct ListNode));
                    l5->next=NULL;
                    l3->next=l5;
                    l3=l5;
                    l1=l1->next;
                    l2=l2->next;
                }
                else{
                    l1=l1->next;
                    l2=l2->next;
                }
            }
            else{
                l3->val=l2->val;
                struct ListNode *l4=(struct ListNode*)malloc(sizeof(struct ListNode));
                l4->val=l1->val;
                l4->next=NULL;
                l3->next=l4;
                l3=l4;
                if((l1->next!=NULL)||(l2->next!=NULL)){
                    struct ListNode *l5=(struct ListNode*)malloc(sizeof(struct ListNode));
                    l5->next=NULL;
                    l3->next=l5;
                    l3=l5;
                    l1=l1->next;
                    l2=l2->next;
                }
                else{
                    l1=l1->next;
                    l2=l2->next;
                }
            }
        }
    }
    return head;
}
           

然后就出现了这种错误。。。

注意事项

• 新建一个节点一定要赋初始值，还要定义*next=null;（因为不定义很容易出现

  runtime error: member access within misaligned address 0xbebebebebebebebe for type 'struct ListNode'

  的错误）
• 新定义的链表可以先把头节点单拎出来赋值，然后剩下的按部就班来，不用再一个一个考虑l1->next或l2->next是否为空了
• 一定提前定义头节点，否则不好找
• 链表排序不好做考虑数组！！
• 一定要考虑输入为空的情况，只有一个空，或两个都空

基本算法

sort函数

void sort(int *a, int l)//a为数组地址，l为数组长度。
{
    int i, j;
    int v;
    for(i = 0; i < l - 1; i ++)
        for(j = i+1; j < l; j ++){
            if(a[i] > a[j])//如前面的比后面的大，则交换。
            {
                v = a[i];
                a[i] = a[j];
                a[j] = v;
            }
        }
}
           

我的题解

先把两个链表合并到一个数组里，再对数组进行排序，最后把数组转移到一个新的链表中

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void sort(int *a, int l)//a为数组地址，l为数组长度。
{
    int i, j;
    int v;
    for(i = 0; i < l - 1; i ++)
        for(j = i+1; j < l; j ++){
            if(a[i] > a[j])//如前面的比后面的大，则交换。
            {
                v = a[i];
                a[i] = a[j];
                a[j] = v;
            }
        }
}
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* head=NULL;
    if(l1||l2){
        struct ListNode *p1=NULL,*p2=NULL;
        if(l1)p1=l1;
        int i=0;
        while(p1){
            i++;
            p1=p1->next;
        }
        if(l2)p2=l2;
        while(p2){
            i++;
            p2=p2->next;
        }
        int a[i];
        int j=0;
        if(l1)p1=l1;
        while(p1){
            a[j]=p1->val;
            j++;
            p1=p1->next;
        }
        if(l2)p2=l2;
        while(p2){
            a[j]=p2->val;
            j++;
            p2=p2->next;
        }
        sort(a,i);
        for(int x=0;x<i;x++)printf("%d\n",a[x]);
        struct ListNode* l3=(struct ListNode*)malloc(sizeof(struct ListNode));
        head=l3;
        l3->val=a[0];
        l3->next=NULL;
        for(int k=1;k<i;k++){
            struct ListNode* l4=(struct ListNode*)malloc(sizeof(struct ListNode));
            l4->val=a[k];
            l4->next=NULL;
            l3->next=l4;
            l3=l4;
        }
    }
    return head;
}
           

大神解法

方法一：除非另一个链表小于当前链表，否则就一直沿着当前链表取下去

//可用递归，相对简洁但是这里用新链表来存储
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef  struct listNode{
      int val;
      struct listNode *next;
 };
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *l3,*l4,*l5;
    l3=(struct listNode *)malloc(sizeof(struct listNode));
    l4=l3;
    while(l1||l2)
    {   
        l5=(struct listNode *)malloc(sizeof(struct listNode));
        if(l1&&l2){
            if(l1->val<=l2->val)
            {
                l5->val=l1->val;
                l1=l1->next;
            }else {
                    l5->val=l2->val;
                    l2=l2->next;
                  }
            }else if(l1){
                     l5->val=l1->val;
                     l1=l1->next;
            }else {
                    l5->val=l2->val;
                    l2=l2->next;
                    }
                l4->next=l5;
                l4=l5;
    }
   l4->next=NULL;
    return l3=l3->next;
}
           

方法二：利用递归

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    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;
    }
}