Mergesort 无法按预期使用链表

Question

前言：

我不关心我的特定合并排序算法的可行性。这不是问题所在。我很好奇为什么我已经编写的程序会以它的方式运行，而不是为什么我应该使用 STL 或其他任何东西。这是为了学习目的。

问题：

我有一个由 Node* 组成的链表结构。我已经为这个特定结构编写了一个半递归合并排序算法（我说半是因为实际排序在技术上是迭代的），但它并没有按照它应该的方式工作（升序排序）。当使用调试器遍历代码时，实际的排序函数 merge() 似乎在整个调用过程中都没有保留新排序的列表，我无法全神贯注地思考如何做到这一点。有人可以解释一下吗？

这是一个最小的可重现示例：

#include <iostream>
struct Link {
    Link(int d=int(), Link* n=nullptr) {
        data = d;
        next = n;
    }
    int         data;
    Link* next;
};

struct LinkList {
  Link* sentinel;
  size_t      size;

 LinkList(Link* h=new Link, size_t s=0) {
    size = s;
    sentinel = h;
  }

  ~LinkList() {
    Link* current = sentinel;
    while (current != 0) {
      Link* next = current->next;
      delete current;
      current = next;
    }
    sentinel = 0;
  }
};

// split into beg and end subLinkList using f/s ptr algorithm
void split(Link* sentinel, Link*& beg, Link*& end) {
    Link* s = sentinel, * f = sentinel->next;

    while (f != NULL) {
        f = f->next;
        if (f != NULL) {
            s = s->next;
            f = f->next;
        }
    }
    beg = sentinel;
    end = s->next;
    s->next = NULL;
}

// conquer (merge) elements from both subLinkLists into new sentinel
Link* merge(Link* beg, Link* end) {
    Link* sentinel = new Link;
    Link* tmp;
    for (tmp = sentinel; beg != NULL && end != NULL; tmp = tmp->next) {
        if (beg-> data < end->data) {
            tmp->next = beg;
            beg = beg->next;
        }
        else {
            tmp->next = end;
            end = end->next;
        }
    }
    if (beg == NULL)
        tmp->next = end;
    else
        tmp->next = beg;
    return tmp;
}

// recursive splitting and merging
Link* sort_merge(Link* sentinel) {
    Link* beg, * end;

    if (sentinel == NULL || sentinel->next == NULL)
        return sentinel;

    split(sentinel, beg, end);
    sort_merge(beg);
    sort_merge(end);

    return merge(beg, end);
}

// helper function calls sort_merge
void sort(LinkList &l) {
  sort_merge(l.sentinel);
}

void print(LinkList &l) {
  for (Link* n = l.sentinel; n != NULL; n = n->next) {
      std::cout << n->data << '\n';
    }
}

int main() {
  // set up linked LinkList 5->4->3->2->1->nullptr
  Link* sentinel = new Link(5 , new Link(4, new Link(3, new Link(2, new Link(1)))));
  LinkList l(sentinel,5);

  sort(l);
  print(l);

  return 0;
}

我想要的输出是

但它输出

Answer 1

几个问题：

merge return是合并列表的最后一个节点，而不是第一个。所以改变：
```
return tmp;
```
至：
```
return head->next;
```
在msort中递归调用的return值被忽略，但它很重要，因为它代表第一个节点after[=41] =] 排序操作。所以改变：

msort(left); msort(right);

至：

left = msort(left); right = msort(right);

在 sort 中 msort 的 return 值被忽略，因此列表的 head 引用永远不会更新。所以改变：

msort(l.head);

至：

l.head = msort(l.head);

Mergesort 无法按预期使用链表

Mergesort not working as intended with linked list

c++

mergesort

pointers

linked-list