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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18