Mergesort for List

题目描述
Please use mergesort to sort a linked list of data.
The linked list is defined as follows.

struct linkedlist{
 int data;
 linkedlist *next;
 };

Please implement the following function.

#include "mergeSort.h"
//sort the list by mergesort and return the head of it
void mergesort(linkedlist *&head, int len){
 //add your code here
}

提示
1->3->2->4->NULL
其中 1 是 head
Yizuodi的答案

#include "mergeSort.h"
#include <iostream>
using namespace std;

linkedlist *mergesort2(linkedlist *head) //将进行归并排序的链表的头指针传入函数
{
    if (head->next == NULL) //一个元素就返回
        return head;
//下面一段代码用于寻找链表的中间位置（虽然我们知道链表的节点个数，不用这么复杂地进行处理
    linkedlist *fast = head->next;// fast指向第2个节点
    linkedlist *slow = head;//slow指向第1个节点
    while (fast != NULL && fast->next != NULL)//fast指针还没移动到最后就一直移动
    {
        fast = fast->next->next; //fast指针移动的速度是slow的两倍
        slow = slow->next;
    }
//下面我们将原来的链表分为两部分 运用递归进行排序处理
    linkedlist *list1 = head;
    linkedlist *list2 = slow->next;
    slow->next = NULL;

//下面准备开始归并处理
    linkedlist *newlist1 = mergesort2(list1);
    linkedlist *newlist2 = mergesort2(list2);

    linkedlist *listpro; //listpro用于保存链表起点
    linkedlist *op;//指针op是进行操作的指针
//我们先向listpro的第一个节点存入左右两个链表的头节点的较小的数
    if (newlist1->data < newlist2->data)
    {
        listpro = newlist1;
        newlist1 = newlist1->next;
    }
    else
    {
        listpro = newlist2;
        newlist2 = newlist2->next;
    }
    op = listpro;
    op->next = NULL;

    while (newlist1 != NULL || newlist2 != NULL)
    {//为了防止有问题，先看看俩链表是否有已经完全连入新链表listpro的
        if (newlist1 == NULL) //链表1的节点已经全部连入新链表
        {
            op->next = newlist2; //那就把链表2直接接上去
            newlist2 = NULL;
        }
        else if (newlist2 == NULL)//链表2的节点已经全部连入新链表
        {
            op->next = newlist1; //那就把链表1直接接上去
            newlist1 = NULL;
        }
        else if (newlist1->data < newlist2->data)//其他情况就按节点存储数值大小决定哪个节点先连入新的链表
        {
            op->next = newlist1; 
            newlist1 = newlist1->next;
            op = op->next;
            op->next = NULL;
        }
        else //如果newlist1->data > newlist2->data
        {
            op->next = newlist2;
            newlist2 = newlist2->next;
            op = op->next;
            op->next = NULL;
        }
    }
    return listpro; //返回新连接好的链表
}

void mergesort(linkedlist *&head, int len)
{
    head = mergesort2(head);
}

zhc的冒泡排序法

#include "mergeSort.h"

void mergesort(linkedlist *&head, int len){ //冒泡排序法
    linkedlist *pi = head ;
    pi=pi->next;
    for(int i=1;i<len;++i){
        linkedlist *pj = head ;
        for(int j=0;j<i;++j){ 
              if( pi->data < pj->data){
                 int t=pj->data;
             pj->data = pi->data;
             pi->data = t;
        }
              pj=pj->next;
    }
        pi=pi->next;
    }
}

zhc的归并排序法：

//Mergesort for List  
#include"mergeSort.h"  
#include<iostream>  
using namespace std ;  

linkedlist* cut(linkedlist* head1) ;  
linkedlist*merge(linkedlist* head1,linkedlist* head2);  
  
void  mergesort(linkedlist *&head , int len){ //len不使用，简便分组  
if(head->next==NULL) return ;//只有一个节点，返回  
   linkedlist *head2  =  cut( head ) ; //分割,并得到head2  
   mergesort(head,len);//排序：若可以继续分组，调用递归  
   mergesort(head2,len);  
   head = merge( head , head2) ;//按顺序合并  
}  
  
linkedlist* cut(linkedlist* head){//分割成2组，并得到head2  
    linkedlist*slow = head;  
    linkedlist*fast = head->next ;  
    while(fast!=NULL && fast->next!=NULL){  
        slow=slow->next;  
        fast=fast->next->next;  
   }//fast走到链表尾时，slow走到链表中间  
    linkedlist *head2  = slow->next ;//得到第二组的头节点head2  
    slow->next = NULL ;//使第一组末尾指向NULL，分割成2组  
    return head2 ;//返回第二组的头节点  
}  
  
linkedlist* merge(linkedlist* head1, linkedlist* head2){  
    if (head1 == NULL)  
        return head2;  
    if (head2 == NULL)  
        return head1;  
    linkedlist* first = NULL;  
    if (head1->data <= head2->data) {  
        first = head1;  
        first->next = merge(head1->next, head2);  
    } else {  
        first = head2;  
        first->next = merge(head1, head2->next);  
    }  
    return first;  
}