链表上的合并排序

Question

我的编码相当糟糕，所以我真的需要一些帮助，因为这个作业要在星期三之前交。我见过 mergesort 通常分为三个函数：（mergesort、sortedmerge、frontbacksplit 等）。但是我的教授基于数组的合并排序是在一个函数中完成的，所以我假设他希望我们也只对这个链表使用一个函数……（除非可以在一个函数中实现一个函数？）我们必须写好函数"struct listnode * mergesort(struct listnode *data)"提交给他。到目前为止我所做的（我认为）是将链表拆分为 2 个子链表，但现在我不知道如何 "recursively" 对它们进行排序。教授告诉我们用 C 或 C++ 编写函数，但是他在下面提供给我们的测试代码是用C语言编写的。

#include <stdio.h>
#include <stdlib.h>

struct listnode { struct listnode * next;
                  long              value; } ;


//This is the function I need to write:
struct listnode * mergesort(struct listnode *data)
{   int temp, finished = 0;
    struct listnode *i, *j, *tail, *head, *ahead, *bhead, *atail, *btail;
    if ( a == NULL )
        return;
    head = data;
    tail = head->next;
    ahead = head;
    bhead = tail;
    i = ahead;
    j = bhead;
    tail = tail->next;
    while ( tail !=NULL ) {
        atail = tail;
        i->next = atail;
        i = i->next;
        tail = tail->next;
        btail = tail;
        j->next = btail;
        j = j->next;
        tail = tail->next;
    }

};

//Testing code provided by professor:
int main(void)
{
   long i;
   struct listnode *node, *tmpnode, *space;
   space =  (struct listnode *) malloc( 500000*sizeof(struct listnode));
   for( i=0; i< 500000; i++ )
   {  (space + i)->value = 2*((17*i)%500000);
      (space + i)->next = space + (i+1);
   }
   (space+499999)->next = NULL;
   node = space;
   printf("\n prepared list, now starting sort\n");
   node = mergesort(node);
   printf("\n checking sorted list\n");
   for( i=0; i < 500000; i++)
   {  if( node == NULL )
      {  printf("List ended early\n"); exit(0);
      }
      if( node->value != 2*i )
      {  printf("Node contains wrong value\n"); exit(0);
      }
      node = node->next;
   }
   printf("Sort successful\n");
   exit(0);
}

Answer 1

一般做法：

if( list contains 0 or 1 item)
    return the list;  // it is already sorted
split the list into halves;
mergesort( first part);
mergesort( second part);
merge sorted parts;
return the merged list;

列表包含 0 或 1 项条件：

head == NULL || head->next == NULL

要拆分列表，您需要找到它的中间部分：

ahead = atail = head;       // first item
btail = head->next;         // second item
while(btail->next != NULL)  // anything left
{
    atail = atail->next;
    btail = btail->next;
    if( btail->next)
        btail = btail->next;
}
bhead = atail->next;        // disconnect the parts
atail->next = NULL;

合并两个排序列表：

if(ahead->value <= bhead->value)  // set the head of resulting list
    head = tail = ahead, ahead = ahead->next;
else
    head = tail = bhead, bhead = bhead->next;

while(ahead && bhead)
    if(ahead->value <= bhead->value)  // append the next item
        tail = tail->next = ahead, ahead = ahead->next;
    else
        tail = tail->next = bhead, bhead = bhead->next;

if(ahead) // once one part got exhausted append the remaining other part
    tail->next = ahead;
else
    tail->next = bhead;

链表上的合并排序

MergeSort on Linked List

c++

mergesort

linked-list