我如何编写将LinkedList＆作为C ++输入的合并排序函数？

Question

这里是我的LinkedList的声明：

struct LinkedList {
LinkedListNode *head, *tail;
LinkedList() { head = tail = NULL; }
~LinkedList() {
    Clear();
} //end-~LinkedList

void Clear() {
    while (head) {
        LinkedListNode* p = head;
        head = head->next;
        delete p;
    } //end-while

    head = tail = NULL;
} //end-Clear

void Append(int key) {
    LinkedListNode* node = new LinkedListNode(key);
    if (tail == NULL) head = tail = node;
    else {
        tail->next = node;
        tail = node;
    } //end-else
} //end-Append
};

这里是我需要在C ++中以这种格式实现的函数体：

void MergeSort(LinkedList& list){ //I need to make merge sort with LinkedList }

这里是测试我的排序算法的代码，但是合并排序不起作用（顺便说一句，我无法更改测试端）。

#define N 1024*32
int A[N];  
typedef void (*SortingFunction)(LinkedList &);

float Test(SortingFunction F, char *msg){
  int B[] = {4, 2, 5, 7, 8, 1, 10, 9, 15, 34, 6, 17, 66, 55, 44, 33};

  LinkedList list;
  for (int i = 0; i < sizeof(B) / sizeof(int); i++) {
      list.Append(B[i]);
  } //end-for

  // Use the sorting algorithm
  F(list);

  printf("Using %s to sort %d numbers...\n", msg, 16);

  // Check the result
  LinkedListNode* p = list.head;
  int S[] = { 1, 2, 4, 5, 6, 7, 8, 9, 10, 15, 17, 33, 34, 44, 55, 66 };
  for (int i = 0; i < sizeof(S) / sizeof(int); i++) {
      if (S[i] != p->key) return 0;
      p = p->next;
  } // end-for

  list.Clear();
  srand((unsigned int)time(NULL));
  int i;
  int min = INT_MAX;
  int max = 0;
  for (i=0; i<100;i++){
      int number = rand();
      list.Append(number);

      if (number<min) min=number;
      else if (number>max) max=number;
  } //end-for

  printf("Using %s to sort %d numbers...", msg, N);
  time_t t1 = time(NULL);
  F(list);
  time_t t2 = time(NULL);
  printf("took %I64d seconds\n", t2-t1);

  // Check the result
  if (list.head->key!=min || list.tail->key!=max) return 0;

  LinkedListNode* q = list.head;
  p = q->next;
  while (p){
    if (q->key > p->key) return 0;
    q = p;
    p = p->next;
  } //end-for

  return 100;
} //end-Test

/****************************************************
 * Main function
 ****************************************************/
int main(){
  float grade = 0;
  printf("======================= TEST4 =======================\n");
  grade += Test(MergeSort, "MergeSort");
  return 0;
} //end-main

这里是我为合并排序编写的代码，但是它不起作用，我认为问题是函数原型。我从互联网上看到的所有示例都使用节点指针作为函数参数。但是在我的系统中，我必须通过LinkedList＆作为引用。我尝试了一些代码，但无法获得结果。另外，这是我尝试但未得到结果的代码。

void MergeSort(LinkedList& list){
    LinkedListNode* myhead = list.head;
    mergeSorting(myhead);

} //end-MergeSort
void mergeSorting(LinkedListNode*& head) {
    if (head->next != NULL)             
    {
        LinkedListNode* head1;
        LinkedListNode* head2 = head;
        int len = getLength(head);
        for (int i = 0; i < len / 2; i++)
        {
            head1 = head2;
            head2 = head2->next;
        }
        head1->next = NULL; 
        head1 = head;
        mergeSorting(head1);
        mergeSorting(head2);
        head = merge(head1, head2);
    }
}
int getLength(LinkedListNode* head) {
    LinkedListNode* cur = head;
    int i = 0;
    for (; cur != NULL; cur = cur->next) {
        i++;
    }
    return i;
}
LinkedListNode* merge(LinkedListNode*& head1, LinkedListNode*& head2) {
    LinkedListNode* newHead;
    if (head1 == NULL) return head2;
    else if (head2 == NULL) return head1;
    if (head1->key < head2->key) {
        newHead = head1;
        newHead->next = merge(head1->next, head2);
    }
    else {
        newHead = head2;
        newHead->next = merge(head1, head2->next);
    }
    return newHead;
}

Answer 1

代码需要稍微不同的方法。 mergeSorting应该将指向节点的指针作为输入参数，并返回指向节点的指针。最后三行应类似于：

        head1 = mergeSorting(head1);
        head2 = mergeSorting(head2);
        return merge(head1, head2);

然后输入呼叫代码：

void MergeSort(LinkedList& list){
    list.head = mergeSorting(list.head);
}

假设允许您进行网络搜索（例如算法），则链表的自下而上合并排序会更快，但是它不是基于用于数组的自下而上合并排序的逻辑。如果感兴趣，Wiki文章提供示例伪代码：

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists