Leetcode学习之链表（5）

开宗明义：本系列基于小象学院林沐老师课程《面试算法 LeetCode 刷题班》，刷题小白，旨在理解和交流，重在记录，望各位大牛指点！

---

Leetcode学习之链表（5）

---

---

1、排序链表的合并（2个）Leetcode 21.

题目来源：$Leetcode \ 21. \ Merge \ Two \ Sorted \ Lists$Leetcode 21. Merge Two Sorted Lists
题目描述：已知两个已排序的链表头节点指针 $I1$I1 和 $l2$l2 ，将这两个链表合并，合并后仍然为有序的，返回合并后的头节点。
要求描述：

思路：
比较 $l1$l1 和 $l2$l2 指向的节点，将较小的节点插入到 $pre$pre 指针后，并向前移动较小节点对应的指针。

测试代码：

#include <stdio.h>
#include <map>
#include <vector>
using namespace std;

struct ListNode {
	int val;
	ListNode *next; //带有随机指针的链表节点
	ListNode(int x) :val(x), next(NULL){}  //构造函数
};

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		ListNode temp_head(0);//设置临时头节点temp_head
		ListNode *pre = &temp_head;//使用pre指针指向temp_head
		while (l1 && l2)//l1与l2同时不为空的时候，对它们进行比较
		{
			if (l1->val < l2->val) {
				pre->next = l1;
				l1 = l1->next;
			}
			else
			{
				pre->next = l2;
				l2 = l2->next;
			}
			pre = pre->next;//pre指向新连接的节点
		}
		if (l1)//如果l1有剩余,将l1接到pre后
		{
			pre->next = l1;
		}
		if (l2)
		{
			pre->next = l2;
		}
		//return &temp_head;
		return temp_head.next; //因为第一个是0
	}
};

int main() {
	ListNode a(1), b(4), c(6), d(0), e(5),f(7);
	a.next = &b;
	b.next = &c;
	d.next = &e;
	e.next = &f;

	Solution solve;
	ListNode *head = solve.mergeTwoLists(&a, &d);
	while (head)
	{
		printf("%d  ",head->val);
		head = head->next;
	}
	system("pause");
	return 0;
}

效果图：

---

2、排序链表的合并（多个）Leetcode 23.

题目来源：$Leetcode \ 23. \ Merge \ K \ Sorted \ Lists$Leetcode 23. Merge K Sorted Lists
题目描述：已知 $k$k 个已排序的链表头节点指针，将这个 $k$k 个链表合并，合并后仍为有序的，返回合并后的头节点：

---

2.1 思路① 暴力合并 O(k^2*n)

方案①：$k$k个链表按顺序合并$k-1$k−1次。设$k$k个链表，平均每个链表有$n$n个节点，那么时间复杂度为：
$(n+n)+(2n+n)+---+((k-1)n+n)=(1+2+3+---+k-1)n+(k-1)n=O(k^2*n)$(n+n)+(2n+n)+−−−+((k−1)n+n)=(1+2+3+−−−+k−1)n+(k−1)n=O(k2∗n)
太暴力，省略！

---

2.2 思路② 排序后相连 O( kN*（logkN）)

方案②：将 $k*n$k∗n 个节点放在 $vector$vector 中，再将 $vector$vector 排序，再将节点顺序相连。
代码实现：

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct ListNode {
	int val;
	ListNode *next; //带有随机指针的链表节点
	ListNode(int x) :val(x), next(NULL){}  //构造函数
};

bool cmp(const ListNode *a, const ListNode *b) {
	return a->val < b->val;
}

class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		vector<ListNode *> node_vec;
		for (int i = 0; i < lists.size(); i++) {
			ListNode *head = lists[i];//遍历k个链表，将节点全部添加到node_vec
			while (head)
			{
				node_vec.push_back(head);
				head = head->next;
			}
		}
		if (node_vec.size() == 0) {
			return NULL;
		}
		//根据节点数值进行排序
		sort(node_vec.begin(),node_vec.end(),cmp);
		for (int i = 1; i < node_vec.size(); i++) {//连接新的链表
			node_vec[i - 1]->next = node_vec[i];
		}
		node_vec[node_vec.size() - 1]->next = NULL;
		return node_vec[0];
	}
};

int main() {
	ListNode a(1), b(4), c(6), d(0), e(5), f(7), g(2), h(3);
	a.next = &b;
	b.next = &c;
	d.next = &e;
	e.next = &f;
	g.next = &h;
	Solution solve;
	vector<ListNode *>lists;  //3个值
	lists.push_back(&a);
	lists.push_back(&d);
	lists.push_back(&g);
	ListNode *head = solve.mergeKLists(lists);
	while (head)
	{
		printf("%d\n",head->val);
		head = head->next;
	}
	system("pause");
	return 0;
}

效果图：

---

2.3 思路③ 分制后相连 O(kN*logk)

方案③：对 $k$k 个链表进行分制，两两进行合并。

测试代码：

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct ListNode {
	int val;
	ListNode *next; //带有随机指针的链表节点
	ListNode(int x) :val(x), next(NULL){}  //构造函数
};

bool cmp(const ListNode *a, const ListNode *b) {
	return a->val < b->val;
}

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		ListNode temp_head(0);//设置临时头节点temp_head
		ListNode *pre = &temp_head;//使用pre指针指向temp_head
		while (l1 && l2)//l1与l2同时不为空的时候，对它们进行比较
		{
			if (l1->val < l2->val) {
				pre->next = l1;
				l1 = l1->next;
			}
			else
			{
				pre->next = l2;
				l2 = l2->next;
			}
			pre = pre->next;//pre指向新连接的节点
		}
		if (l1)//如果l1有剩余,将l1接到pre后
		{
			pre->next = l1;
		}
		if (l2)
		{
			pre->next = l2;
		}
		//return &temp_head;
		return temp_head.next; //因为第一个是0
	}

	ListNode* mergeKLists(vector<ListNode *>& lists) {
		if (lists.size() == 0) {
			return NULL;//如果lists为空，返回NULL
		}
		if (lists.size() == 1) {
			return lists[0];//如果只有一个lists，则返回头指针  
		}
		if (lists.size() == 2) {
			return mergeTwoLists(lists[0], lists[1]);
		}   
		int mid = lists.size() / 2;
		vector<ListNode *> sub1_lists;//lists拆分为两个lists
		vector<ListNode *> sub2_lists;
		for (int i = 0; i < mid; i++) {
			sub1_lists.push_back(lists[i]);
		}
		for (int i = mid; i < lists.size(); i++) {
			sub2_lists.push_back(lists[i]);
		}
		ListNode *l1 = mergeKLists(sub1_lists);
		ListNode *l2 = mergeKLists(sub2_lists);
		return mergeTwoLists(l1, l2);//分制处理
	}
};

int main() {
	ListNode a(1), b(4), c(6), d(0), e(5), f(7), g(2), h(3);
	a.next = &b;
	b.next = &c;
	d.next = &e;
	e.next = &f;
	g.next = &h;
	vector<ListNode *>lists;  //3个值
	lists.push_back(&a);
	lists.push_back(&d);
	lists.push_back(&g);
	Solution solve;
	ListNode *head = solve.mergeKLists(lists);

	while (head)
	{
		printf("%d\n", head->val);
		head = head->next;
	}
	system("pause");
	return 0;
}

效果图：