【数据结构】_链表经典算法OJ：合并两个有序数组

目录

1. 题目描述及链接

2. 解题思路

3. 程序

3.1 第一版

3.2 第二版

1. 题目描述及链接

题目链接：21. 合并两个有序链表 - 力扣（LeetCode）

题目描述：

将两个升序链表合并为一个新的 升序 链表并返回。

新链表是通过拼接给定的两个链表的所有节点组成的。

2. 解题思路

总思路：

创建一个新的链表。定义两个结构体指针变量，分别指向两个链表待比较结点，遍历原链表，依次对比选出值更小的结点依次尾插到新链表。

具体实现思路：

（1）由于需要依次对比两链表结点的大小值，故创建两个指针变量l1与l2分别用于指向链表1和链表2的当前比较的结点。

（2）由于需要将较小值结点尾插到新链表，故需创建指针变量newTail指向当前新链表的尾结点，每次插入一个结点就更新一次newTail。

且需返回新链表的头结点，故需创建指针变量newTail指向新链表的尾结点。

（3）直至对链表1或链表2完成遍历，即l1或l2为空，则此时将不为空的链表后续的若干结点直接拼接到新链表的newTail之后即可。

（4）考虑特殊情况：链表1为空或链表2为空时，根据当前代码逻辑，l1或l2其中一个为NULL，则newTail为空，若执行newTail->next会导致对空指针的解引用，故需单独讨论处理。

处理逻辑为：若链表1为空，则直接返回链表2的头结点；

若链表2为空，则直接返回链表1的头结点；

3. 程序

3.1 第一版

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 判空
    if(list1==NULL){
        return list2;
    }
    if(list2==NULL){
        return list1;
    }
    ListNode* l1=list1;
    ListNode* l2=list2;
    // 新链表
    ListNode* newHead=NULL;
    ListNode* newTail=NULL;
    while(l1 && l2){
        if(l1->val<l2->val){
            // 尾插l1
            if(newHead==NULL){
                newHead=newTail=l1;
            }else{
                newTail->next=l1;
                newTail=newTail->next;
            }
            l1=l1->next;
        }else{
            // 尾插l2
            if(newHead==NULL){
                newHead=newTail=l2;
            }else{
                newTail->next=l2;
                newTail=newTail->next;
            }
            l2=l2->next;
        }
    }
    // l1或l2为空
    if(l2){
        newTail->next=l2;
    }
    if(l1){
        newTail->next=l1;
    }
    return newHead;
}

3.2 第二版

在上文程序中的while循环体内，易观察到while循环体内的代码重复：

优化思路如下：

此处重复原因：新链表存在空和非空两种情况，故而可令newHead和newTail初始状况不为空：

初始化时为newHead何newTail动态申请一个结点的空间，但不存储有效数据。

同时最终返回值也不再是newHead，而是newHead->next；

解题程序如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 判空
    if(list1==NULL){
        return list2;
    }
    if(list2==NULL){
        return list1;
    }
    ListNode* l1=list1;
    ListNode* l2=list2;
    // 新链表
    ListNode* newHead,*newTail;
    newHead=newTail=(ListNode*)malloc(sizeof(ListNode));
    while(l1 && l2){
        if(l1->val<l2->val){
            // 尾插l1
            newTail->next=l1;
            newTail=newTail->next;
            l1=l1->next;
        }else{
            // 尾插l2
            newTail->next=l2;
            newTail=newTail->next;
            l2=l2->next;
        }
    }
    // l1或l2为空
    if(l2){
        newTail->next=l2;
    }
    if(l1){
        newTail->next=l1;
    }
    // 动态申请的空间手动释放
    ListNode* ret=newHead->next;
    free(newHead);
    newHead=NULL;
    return ret;
}