题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
解法
这里我们使用迭代的方式将两个有序链表合并成一个有序链表。首先判断两个输入的链表是否为空，如果有一个为空则直接返回另一个链表。然后定义两个指针l1和l2分别指向两个链表的头部，再定义一个新的链表头指针newHead和尾指针newTail。
在循环中，比较l1和l2当前节点的值，将较小的节点插入到新链表中，并更新newTail指针。循环直到其中一个链表遍历完毕。最后判断剩余的链表，将剩余的节点直接连接到新链表的尾部。
最后返回新链表的头部即可。这种方法的时间复杂度为O(m+n)，其中m和n分别为两个链表的长度。
/** * 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) { // 判断list1或者list2是否为空表，如果是则直接返回另一个表即可（基于原先的表已经为有序，所以无需重新排序） if (list1 == NULL) { return list2; } if (list2 == NULL) { return list1; } ListNode *l1, *l2; l1 = list1, l2 = list2; ListNode *newHead, *newTail; newHead = 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; } } // 跳出循环存在两种情况： // A.l1空 l2不为空 if (l1) { newTail->next = l1; // newTail =newTail->next(指向的是新一串的头结点) } // B.l2空 l1不为空 if (l2) { newTail->next = l2; // newTail = newTail->next; } return newHead; }
