题目描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}

题解1：一次迭代

代码

struct ListNode {
	int val;
	struct ListNode* next;
	ListNode(int x) :
		val(x), next(NULL) {
	}
};
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
	ListNode* myhead = new ListNode(-1);
	ListNode* cur = myhead;
	while (pHead1 && pHead2)
	{
		if (pHead1->val <= pHead2->val) {
			cur->next = pHead1;//cur指向较小的节点
			pHead1 = pHead1->next;//pHead1向后移动
			cur = cur->next;//cur向后移动
		}
		else {
			cur->next = pHead2;
			pHead2 = pHead2->next;
			cur = cur->next;
		}
	}
	//当某个链表提前为空时候，如{1，2，3}和{2，4，5，6，7}
	//要将第二个链表接上
	cur->next = pHead1 ? pHead1 : pHead2;//pHead1为空，则等于pHead1
	return myhead->next;
}

题解2：使用辅助数组

算法i思路：

先把两个链表的数据全部存放在数组中
然后进行排序
最后一次创建鑫的链表

代码

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
	vector<int> v;
	if (pHead1 == NULL) return pHead2;
	if (pHead2 == NULL) return pHead1;
	while (pHead1)
	{
		v.push_back(pHead1->val);
		pHead1 = pHead1->next;
	}
	while (pHead2)
	{
		v.push_back(pHead2->val);
		pHead2 = pHead2->next;
	}
	sort(v.begin(), v.end());
	ListNode* myhead = new ListNode(-1);
	ListNode* cur = myhead;
	for (int i= 0; i < v.size(); i++)
	{
		cur->next = new ListNode(v[i]);
		cur = cur->next;
	}
	return myhead->next;
}