合并排序通常用于对链表进行排序。链表缓慢的随机访问性能使得其他一些算法（如快速排序）表现不佳，而其他算法（如堆排序）则完全不可能。
令 head 为链表的第一个要排序的节点，headRef 为 head 的指针。请注意，我们需要在 MergeSort() 中引用 head，因为下面的实现更改了下一个链接以对链表进行排序（不是节点上的数据），因此如果原始头部的数据不是链表中的最小值。
合并排序（headRef） 1）如果head为NULL或链表中只有一个元素 然后返回。 2）否则将链表分成两半。 FrontBackSplit(head, &a, &b); /* a 和 b 是两半 */ 3) 将 a 和 b 的两半排序。 归并排序（一）； 归并排序(b); 4) 合并已排序的 a 和 b（使用此处讨论的 SortedMerge() ） 并使用 headRef 更新头指针。 *headRef = SortedMerge(a, b);
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; Node* SortedMerge(Node* a, Node* b); void FrontBackSplit(Node* source, Node** frontRef, Node** backRef); void MergeSort(Node** headRef) { Node* head = *headRef; Node* a; Node* b; if ((head == NULL) || (head->next == NULL)) { return; } FrontBackSplit(head, &a, &b); MergeSort(&a); MergeSort(&b); *headRef = SortedMerge(a, b); } Node* SortedMerge(Node* a, Node* b) { Node* result = NULL; if (a == NULL) return (b); else if (b == NULL) return (a); if (a->data <= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return (result); } void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) { Node* fast; Node* slow; slow = source; fast = source->next; while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } } *frontRef = source; *backRef = slow->next; slow->next = NULL; } void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } int main() { Node* res = NULL; Node* a = NULL; push(&a, 15); push(&a, 10); push(&a, 5); push(&a, 20); push(&a, 3); push(&a, 2); MergeSort(&a); cout << "Sorted Linked List is: \n"; printList(a); return 0; }
输出：
Sorted Linked List is: 2 3 5 10 15 20
时间复杂度： O(n*log n)\
空间复杂度： O(n*log n)
方法 2： 这种方法更简单，使用 log n 空间。
合并排序（）：
- 如果链表的大小为 1，则返回头部
- 使用乌龟和兔子的方法找到中间
- 将 mid 的 next 存储在 head2 中，即右子链表。
- 现在使下一个中点为空。
- 对左右子链表递归调用mergeSort()，存储左右子链表的新头。
- 给定左右子链表的新头的参数调用 merge() 并存储合并后返回的最终头。
- 返回合并链表的最终头。
合并（头1，头2）：
- 取一个指针 say merge 将合并的列表存储在其中并在其中存储一个虚拟节点。
- 取一个指针 temp 并为其分配合并。
- 如果 head1 的数据小于 head2 的数据，则将 head1 存储在 temp 的 next 并将 head1 移动到 head1 的 next。
- 否则将 head2 存储在 temp 的下一个并将 head2 移动到 head2 的下一个。
- 将 temp 移动到 temp 的下一个。
- 重复步骤 3、4 和 5，直到 head1 不等于 null 且 head2 不等于 null。
- 现在将第一个或第二个链表的任何剩余节点添加到合并的链表中。
- 返回合并的下一个（这将忽略虚拟并返回最终合并链表的头部）
#include<iostream> using namespace std; struct Node{ int data; Node *next; }; void insert(int x,Node **head) { if(*head == NULL){ *head = new Node; (*head)->data = x; (*head)->next = NULL; return; } Node *temp = new Node; temp->data = (*head)->data; temp->next = (*head)->next; (*head)->data=x; (*head)->next=temp; } void print(Node *head) { Node *temp=head; while(temp!=NULL) { cout<<temp->data<<" "; temp = temp->next; } } Node *merge(Node *firstNode,Node *secondNode) { Node *merged = new Node; Node *temp = new Node; merged = temp; while(firstNode != NULL && secondNode != NULL) { if(firstNode->data<=secondNode->data) { temp->next = firstNode; firstNode = firstNode->next; } else { temp->next = secondNode; secondNode = secondNode->next; } temp = temp->next; } while(firstNode!=NULL) { temp->next = firstNode; firstNode = firstNode->next; temp = temp->next; } while(secondNode!=NULL) { temp->next = secondNode; secondNode = secondNode->next; temp = temp->next; } return merged->next; } Node *middle(Node *head) { Node *slow = head; Node *fast = head->next; while(slow->next != NULL && (fast!=NULL && fast->next!=NULL)) { slow = slow->next; fast = fast->next->next; } return slow; } Node *sort(Node *head){ if(head->next == NULL) { return head; } Node *mid = new Node; Node *head2 = new Node; mid = middle(head); head2 = mid->next; mid->next = NULL; Node *finalhead = merge(sort(head),sort(head2)); return finalhead; } int main(void) { Node *head = NULL; int n[]={7,10,5,20,3,2}; for(int i=0;i<6;i++) { insert(n[i],&head); } cout<<"\nSorted Linked List is: \n"; print(sort(head)); return 0; }
输出：
Sorted Linked List is: 2 3 5 7 10 20
时间复杂度：O(n*log n)
空间复杂度： O(log n)
