题目描述21. 合并两个有序链表 - 力扣（LeetCode）：
答案展示:
迭代：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode* newhead = malloc(sizeof(struct ListNode));
newhead->next = list1;
struct ListNode*pcur1 = newhead;
//只要涉及两个对象将一个放到另一个中，及一定有一个到头另一个还没到的两种情况
while (pcur1->next)//有两个就说明，有两种走到头的方式
{
if(!list2)
{
list2 = newhead->next;
break;
}
if(pcur1->next->val>=list2->val)
{
struct ListNode*tmp = pcur1->next;
pcur1->next = list2;
list2 = tmp;
}
pcur1 = pcur1->next;
if(!pcur1->next)
{
pcur1->next = list2;
list2 = newhead->next;
break;
}
}
return list2;
}
递归：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if(!list1||!list2)
{
if(list1)
{
list1->next = mergeTwoLists(list1->next,list2);
return list1;
}
else if(list2)
{
list2->next = mergeTwoLists(list1,list2->next);
return list2;
}
else
return NULL;
}
else
{
if(list1->val>=list2->val)
{
list2->next = mergeTwoLists(list1,list2->next);
return list2;
}
else
{
list1->next = mergeTwoLists(list1->next,list2);
return list1;
}
}
}
官方递归：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/merge-two-sorted-lists/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
收获
- 这道题的情况很多，值得多复习训练。体现在尝试迭代时，我使用的方法是两链表相互交换，而对应的很多边界情况未能考虑周全，而后重试时，通过调换某些特殊变量的位置，同时添加判断才得以解决。另外，迭代还可以是创建一个哨兵位，直接遍历两个链表，进行尾插，还可以是每个链表使用三个指针遍历得出。
- 以后写完代码不论多自信是对的，都要在提交前最后走一遍逻辑
- 在尝试迭代方法时，为了避免冗余代码，长时间死磕，最后部分地方还是写的比较冗余，但通过学习官方题解确实让我眼前一亮，有些逻辑可以不用“直译”，也可以“意译”，如官解的前两个分支，就很好的解决了两个list都是NULL的情况，而我使用的则是直接将其提出额外做一个分支，可能有时候，可以先把一种情况不讨论，优先实现其他，最后在倒过头来发现，也解决了未考虑的。
