LeetCode Algorithm 剑指 Offer 25. 合并两个排序的链表

剑指 Offer 25. 合并两个排序的链表

Ideas

这题让我想到了归并排序：

1. 划分问题：把序列分成元素个数尽量相等的两半；
2. 递归求解：把两半元素分别排序；
3. 合并问题：把两个有序表合并成一个。

捞一张之前的老图来看一下归并排序的过程： 这题相当于归并排序的最后一步：合并两个有序表。

循环比对两个链表头的值，取小的那个添加到新的链表的尾部。

C++

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* res = new ListNode(0), *p = res; while (l1 && l2) { if (l1->val < l2->val) { p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } p = p->next; } p->next = l1 ? l1 : l2; return res->next; } };