题目描述
输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
数据范围
链表长度 [0,500]。
样例
输入：1->3->5 , 2->4->5 输出：1->2->3->4->5->5
方法一：二路归并 O(n)
我们可以创建一个头指针，然后将两个链表用这个头指针串起来。我们拿样例举例，看看是如何实现的（下面的图中等于是另外创建了一个链表，实际上代码只用将两个链表的结点串起来即可，不用重新开辟 O(n) 的空间，但是为了更直观的给大家展示效果，我将 head 的链表单独拎了出来）：
第一步： 创建一个新的头结点
第二步： 让 l1 和 l2 从头往后遍历链表，每次遍历的时候如果 l1 指向的结点值比 l2 指向的结点值小就将 l1 指向的结点加入 head 链表中；反之，就将 l2 指向的结点加入到 head 链表中。
（1）1 小于 2 ，将 1 加入链表中。
（2）2 小于 3 ，将 2 加入链表中。
（3）3 小于 4 ，将 3 加入链表中。
（4）4 小于 5 ，将 4 加入链表中。
（5）最后再将两个 5 分别加入到链表中。
第三步： 返回最终得到的链表，注意这里要返回的是 head->next ，因为 head 是我们创建出来的结点。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* merge(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(0); ListNode* temp = head; while (l1 != NULL && l2 != NULL) { if (l1->val < l2->val) { temp->next = l1; l1 = l1->next; } else { temp->next = l2; l2 = l2->next; } temp = temp->next; } if (l1 != NULL) temp->next = l1; else if (l2 != NULL) temp->next = l2; return head->next; } };
欢迎大家在评论区交流~
