一、问题描述
二、解题思路详解
合并两个有序链表的思路
创建一个新的链表，将两个链表的节点元素按大小顺序逐个尾插到新的链表中，最后返回新链表的首节点地址
解题的步骤
- 先对两个链表进行判空，如果任意一个链表为空，直接返回另一个链表首节点地址
- 创建两个指针用来指向新链表的首节点和尾节点，初始都指向NULL
- 再创建两个指针p1 p2用来遍历两个有序链表，初始分别指向两个链表的首节点
- 然后进入while循环，当两个链表都未遍历完成时执行循环，先比较p1 和p2指向的节点的元素大小，将较小的节点插入新链表的尾部
- 插入的过程——先判断新链表是否为空
如果为空，新链表的首尾指针都指向该节点
如果不为空，执行尾插。将新链表尾节点的next指针执行该节点，再将尾指针向后移动
完成一个节点插入后，将该节点所属的链表的遍历指针向后移动- 出循环后，说明两个链表其中有一个先遍历完成了
此时进行判断，哪个指针指向空，就将另一个链表剩余节点挂在新链表尾部- 最后，返回新链表的首节点指针
代码的优化
存在问题——每次插入都要判断链表是否为空
解决办法——创建不存储数据的头结点，让链表不为空
不要忘记使用完成后对动态申请空间释放
最后返回新链表第一个有效节点的地址
三、C语言代码实现
struct ListNode { //单链表结构 int val; struct ListNode* next; }; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (list1 == NULL)//先判断两个链表是否为空 return list2; if (list2 == NULL) return list1; struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));//新链表头节点指针 struct ListNode* newtail = newhead;//新链表尾指针 struct ListNode* p1 = list1;//遍历两个链表的指针 struct ListNode* p2 = list2; while (p1 && p2)//两个链表都不为空执行循环 { //哪个链表节点数据小，就将其尾插到新链表 if (p1->val > p2->val) { newtail->next = p2; p2 = p2->next; } else { newtail->next = p1; p1 = p1->next; } newtail = newtail->next;//新链表尾指针向后移动 } //一定有一个链表先走到空，出循环后将另一个链表剩余节点尾插到新链表 if (p1 == NULL) { newtail->next = p2; } if (p2 == NULL) { newtail->next = p1; } struct ListNode* ret = newhead->next; free(newhead); newhead = NULL; return ret; }
