合并两个有序链表，是链表的经典题之一 ，这里给出一种经典解法
想法一
创建head和tail两个指针，从头比较两个链表，取小的尾插，注意一开始指针的初始化，接着就是不断利用tail指针，链接比较之中较小的节点，然后tail指针和list指针都往后移动一个节点
这是尾插list1的部分，小伙伴可以仿照着写尾插list2的部分哦~
当循环结束时，总有一个链表不为空，那就直接将其链接在tail所在节点的后面
最后，要注意如果有空链表的存在 ，即跳过循环时tail为NULL，则直接让head为另一个链表的头部，返回
同样，这是list1不为空时的判断， 小伙伴可以仿照着写尾插list2的部分哦~
完整代码如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* head = NULL; struct ListNode* tail = NULL; while (list1 && list2) { if (list1->val < list2->val) { if (tail) { tail->next = list1; tail = tail->next; } else { head = tail = list1; } list1 = list1->next; } else { if (tail) { tail->next = list2; tail = tail->next; } else { head = tail = list2; } list2 = list2->next; } } if (list1) { if (!tail) { head = list1; } else { tail->next = list1; } } if (list2) { if (!tail) { head = list2; } else { tail->next = list2; } } return head; }
想法二
这里可以创建哨兵位，可以避免head和tail指针初始化的讨论和判断
看看，判断流程简化了不少吧~
不过最后不能直接返回head，因为那是哨兵位，所以我们要删除哨兵位，将head指向头节点返回
完整代码如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (!list1) { return list2; } if (!list2) { return list1; } struct ListNode* head = NULL; struct ListNode* tail = NULL; //哨兵位 head = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); while (list1 && list2) { if (list1->val < list2->val) { tail->next = list1; tail = tail->next; list1 = list1->next; } else { tail->next = list2; tail = tail->next; list2 = list2->next; } } if (list1) { tail->next = list1; } if (list2) { tail->next = list2; } struct ListNode* del = head; head = head->next; free(del); return head; }
