【数据结构】_链表经典算法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){// 尾插l1if(newHead==NULL){newHead=newTail=l1;}else{newTail->next=l1;newTail=newTail->next;}l1=l1->next;}else{// 尾插l2if(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){// 尾插l1newTail->next=l1;newTail=newTail->next;l1=l1->next;}else{// 尾插l2newTail->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;
}