【问题描述】
有一个含n(n<=200000)个整数的无序序列,采用链表的二路归并排序实现递增排序
【输入形式】
一行字符串,包含多个整数,每个数之间用空格分开。
【输出形式】
递增排序的结果,每个数之间用空格分开。
【样例输入】
9 4 7 6 2 5 8 1 3
【样例输出】
1 2 3 4 5 6 7 8 9
【样例说明】
测试数据的文件名为in.txt,输出文件名为out.txt
【解题思路】
参考LeetCode148——排序链表
利用递归的方法进行排序
利用双指针法,对原链表进行分割,分成两个子链表,再对子链进行分割,直到只有一个结点,此时是递归终点。
然后进行合并,将两个有序链表合并为一个有序链表
具体过程如下图:
【完整代码】
(测试数据从"in.txt"文件中读取,结果输出到"out.txt"文件中)
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
typedef struct LNode
{
int data;
struct LNode* next;
}LNode,*LinkList;
void InitList(LinkList& L)
{
L = NULL;
}
void CreateList(LinkList& L, vector<int>& data) //尾插法创建不带头节点的单链表
{
LNode* r = L;
LNode* s;
for (int i = 0; i < data.size(); i++)
{
s = new LNode;
s->data = data[i];
s->next = NULL;
if (r == NULL)
{
r = s;
L = s;
}
else
{
r->next = s;
r = s;
}
}
}
LinkList MergeList(LinkList& a, LinkList& b) //合并两有序链表
{
LNode* head = new LNode;
head->next = NULL;
LNode* r = head;
while (a != NULL && b != NULL)
{
if (a->data < b->data)
{
r->next = a;
a = a->next;
}
else if(a->data > b->data)
{
r->next = b;
b = b->next;
}
else //两数相等时,不去重(该操作是因为提交作业时发现答案中依然保留了重复的数)
{
r->next = a;
a = a->next;
r = r->next;
r->next = b;
b = b->next;
}
r = r->next;
}
//最后要注意将没有遍历完的链表直接连接到新链表末尾
if (a)
r->next = a;
if (b)
r->next = b;
return head->next;
}
LinkList SortList(LinkList& L)
{
//链表为空或者只有一个结点,直接返回
if (L == NULL || L->next == NULL)
return L;
//利用快慢指针法找到中间结点
LNode* slow = L;
LNode* fast = L->next;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
//分割为两条子链
LNode* mid = slow->next;
slow->next = NULL;
//对两条子链进行排序
LNode* left = SortList(L);
LNode* right = SortList(mid);
//合并子链
return MergeList(left, right);
}
int main()
{
ifstream ifs;
ifs.open("in.txt");
if (!ifs.is_open())
cout << "open file failed!" << endl;
vector<int>data;
int temp=0;
while (ifs >> temp)
data.push_back(temp);
ifs.close();
LinkList L;
InitList(L);
CreateList(L, data);
LinkList ans=SortList(L);
ofstream ofs;
ofs.open("out.txt");
LNode* p = ans;
while (p)
{
ofs << p->data << " ";
p = p->next;
}
ofs.close();
}
标签:链表,归并,NULL,LNode,next,LinkList,数据结构,data,线性表
From: https://blog.csdn.net/2402_84389946/article/details/142303470