力扣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;
    }
}