合并有序链表

方法1：/链表转数组，排序，在数组转链表=需借助辅助空间/

#include 
#include 
using namespace std;

typedef struct Node{
	struct Node* next;
	int val;
}node;

vector<int> ListToArr(node* head1,node* head2)
{
	vector<int> res_vec;
	if (head1 == nullptr && head2==nullptr) return res_vec;
	if (head1 != nullptr)
	{
		node* phead = head1;
		while (phead != nullptr)
		{
			res_vec.push_back(phead->val);
			phead = phead->next;
		}
	}
	if (head2 != nullptr) {
		node* phead2 = head2;
		while (phead2 != nullptr)
		{
			res_vec.push_back(phead2->val);
			phead2 = phead2->next;
		}
	}
	return res_vec;
}
void maopao_Sort(vector<int>& vec)
{
	for (int i=0;i<vec.size()-1;i++)
	{
		for (int j=i+1;j>0;j--)
		{
			if (vec[j - 1] > vec[j])
			{
				int temp = vec[j - 1];
				vec[j - 1] = vec[j];
				vec[j] = temp;
			}
		}
	}
}
Node* ArrToList(vector<int>& vec)//数组转链表
{
	node* NewNode = new node;
	NewNode->next = nullptr;
	NewNode->val = vec[0];
	node* head = NewNode;
	node* phead = head;
	for (int i = 1; i < vec.size(); i++)
	{
		node* NewNode = new node;
		NewNode->next = nullptr;
		NewNode->val = vec[i];
		phead->next = NewNode;
		phead = phead->next;
	}
	return head;
}
void Print_List(node* head)//打印链表
{
	node* temp = head;
	while (temp != nullptr)
	{
		if (temp->next == nullptr)
			cout << temp->val << endl;
		else
			cout << temp->val << "->";
		temp = temp->next;
	}
}
int main(void)
{
	vector<int> Arr1 = { 1,2,4 };
	vector<int> Arr2 = { 1,3,4 };
	node* head1 = ArrToList(Arr1);
	Print_List(head1);
	node* head2 = ArrToList(Arr2);
	Print_List(head2);

	vector<int> Arr3 = ListToArr(head1,head2);
	maopao_Sort(Arr3);

	node* head3= ArrToList(Arr3);
	Print_List(head3);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

方法2：/直接使用其中一个链表做载体/

#include 
#include 
using namespace std;

typedef struct Node {
	struct Node* next;
	int val;
	Node(int x) : val(x), next(NULL) {}//构造形参列表
}node;

Node* ArrToList(vector<int>& vec)//数组转链表
{
	node* NewNode = new node(vec[0]);
	node* head = NewNode;
	node* phead = head;
	for (int i = 1; i < vec.size(); i++)
	{
		node* NewNode = new node(vec[i]);
		phead->next = NewNode;
		phead = phead->next;
	}
	return head;
}
void Print_List(node* head)//打印链表
{
	node* temp = head;
	while (temp != nullptr)
	{
		if (temp->next == nullptr)
			cout << temp->val << endl;
		else
			cout << temp->val << "->";
		temp = temp->next;
	}
}
node* Merge_List(node* head1, node* head2)
{
	node* dummy = new node(-1);
	node* head = dummy;
	while (head1!=nullptr && head2!=nullptr)
	{
		if (head1->val > head2->val)
		{
			head->next = head2;
			head2 = head2->next;
		}
		else
		{
			head->next = head1;
			head1 = head1->next;
		}
		head = head->next;
	}
	if (head1 != nullptr) head->next = head1;
	if (head2 != nullptr) head->next = head2;
	return dummy->next;
}
void main(void)
{
	vector<int> Arr1 = { 1,2,4 };
	vector<int> Arr2 = { 1,3,4 };
	node* head1 = ArrToList(Arr1);
	Print_List(head1);
	node* head2 = ArrToList(Arr2);
	Print_List(head2);

	node* head3 = Merge_List(head1, head2);
	Print_List(head3);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69