归并排序算法c++链表
时间: 2025-01-14 17:08:52 浏览: 50
归并排序是一种分治策略的典型应用,它将待排序的序列分成两个较小的部分,分别对这两个部分进行排序,然后合并它们。对于链表数据结构,由于其非随机访问的特点,我们可以将其看作是一个元素节点的数组,按照常规的归并排序方法稍作调整。
在C++中,针对链表实现归并排序的基本步骤如下:
1. **拆分链表**:首先将链表一分为二,直到每个子链表只有一个节点,这是递归的基础条件。
2. **排序子链表**:对每个子链表分别进行递归排序,通常采用比较相邻节点的方式,将它们按顺序排列。
3. **合并子链表**:将两个已排序的子链表合并成一个有序链表。遍历两个子链表,每次取当前节点最小的那个添加到结果链表,并移动指向下一个未处理节点。
4. **递归回溯**:当所有子链表只剩下一个时,递归结束,返回链表头部作为最终的有序链表。
下面是一个简单的C++链表归并排序的例子:
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1 || !l2) return (l1 ? l1 : l2);
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
ListNode* mergeSortList(ListNode* head) {
if (!head || !head->next) return head; // 如果链表只有一个元素或为空,则无需排序
// 找到中间节点
ListNode* middle = findMiddle(head);
ListNode* tail = middle->next;
// 分割链表
middle->next = nullptr;
// 对两半链表分别进行排序
ListNode* sorted1 = mergeSortList(head);
ListNode* sorted2 = mergeSortList(tail);
// 合并两个已排序链表
return mergeTwoLists(sorted1, sorted2);
}
ListNode* findMiddle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
```
阅读全文
相关推荐


















