0021-合并两个有序链表

合并两个有序链表

方案一

---

具体思想就是新建一个链表，然后比较两个链表中的元素值，把较小的那个链到新链表中，由于两个输入链表的长度可能不同，所以最终会有一个链表先完成插入所有元素，则直接另一个未完成的链表直接链入新链表的末尾

借助单链表实现

C-源代码

---

#include <stdlib.h>

#include "LinkList.h"

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL) {
        return l2;
    }
    
    if (l2 == NULL) {
        return l1;
    }
    
    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    head->next = NULL;
    
    struct ListNode *p = head;
    
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            p->next = l1;
            l1 = l1->next;
        }
        else {
            p->next = l2;
            l2 = l2->next;
        }
        p = p->next;
    }
    
    if (l1 != NULL) {
        p->next = l1;
    }
    
    if (l2 != NULL) {
        p->next = l2;
    }
    
    p = head->next;
    free(head);
    
    return p;
}

void test_0021(void) {
    int arr1[3] ={ 4, 2, 1 };
    int arr2[3] ={ 4, 3, 1 };
    struct ListNode *l1 = createNode(arr1, sizeof(arr1) / sizeof(arr1[0]));
    struct ListNode *l2 = createNode(arr2, sizeof(arr2) / sizeof(arr2[0]));
    printNode(l1);
    printNode(l2);
    
    struct ListNode *ret = mergeTwoLists(l1, l2);
    printNode(ret);
}

参考Grandyang