单链表归并排序

/* 输入元素，-1结束输入 */ #include <iostream> #include <malloc.h> using namespace std; typedef struct LNode { int data; struct LNode *next; } *LinkList; void List_TailInsert(LinkList &L) { int c; LinkList p; L = (LinkList) malloc (sizeof(LNode)); p = L; while(cin>>c && c!=-1) { LinkList s = (LinkList) malloc (sizeof(LNode)); s->data = c; p->next = s; p = s; } p->next = NULL; } void PrintList(LinkList L) { LinkList p = L->next; while(p) { cout << p->data << " "; p = p->next; } cout << endl; } void PrintList1(LinkList L) { LinkList p = L; while(p) { cout << p->data << " "; p = p->next; } cout << endl; } LinkList s[20]; int top = -1; void MergeSort(LinkList &L) { LinkList p, q; p = L->next; if(p->next == NULL) //只有一个结点 { return; } else //不止一个结点 { while(p) { q = p->next; LinkList t = p; int top1 = top; while(q) { if(p->data <= q->data){ p=p->next; q=q->next; } else { s[++top] = t; p->next = NULL; p = q; break; } } if(top1 == top){ //当前的序列完全升序 s[++top] = t; p->next = NULL; p = q; break; } } } } void Merge(LinkList &L) { int i = 0; LinkList p; while(i+1 <= top) { p = L; LinkList q, p1; p1 = s[i]; q = s[i+1]; while(p1 && q) { if(p1->data < q->data){p->next=p1; p1=p1->next;} else {p->next=q; q=q->next;} p = p->next; } if(p1) p->next = p1; if(q) p->next = q; s[++i] = L->next; } } int main() { LinkList L; List_TailInsert(L); MergeSort(L); Merge(L); PrintList(L); return 0; }