链表排序方式的不同之处

Question

我正在考虑排序链表的方法，我想出了两种不同的方法(使用BubbleSort，因为我在编程方面相对较新，它对我来说是最简单的算法)。示例结构:

struct node {
  int value;
  node *next;
};

两个不同的方法:

• 重新排列列表元素
• 做一些类似swap(root->value, root->next->value)的事情

我在谷歌上搜索了一下这个主题，从表面上看，第一种方法似乎更受欢迎。根据我的经验，重新排列列表比简单地交换实际节点值要复杂得多。重新排列整个列表有什么好处吗?如果有，是什么好处?

Answer 1

我能想到两个优点:

1)可能存在其他指针，指向该列表中的节点。如果你重新排列列表，这些指针仍然会指向它们在排序前所指向的相同值;如果你交换值，它们就不会。(这两种方法哪个更好取决于你的设计细节，但在某些设计中，如果它们仍然指向相同的值，那就更好了。)

Answer 2

正如Beta所回答的那样，重新排列节点(通过下一个指针)比交换节点数据更好。

如果实际使用冒泡排序或任何通过指针"交换"节点的排序，则首先将下一个(或头)指针交换到要交换的两个节点，然后交换这两个节点的下一个指针。这既可以处理相邻节点的情况，即旋转3个指针，也可以处理交换2对指针的正常情况。

另一个简单的选项是为已排序的列表创建一个新的空列表(node * pNew = NULL;)。每次从原始列表中删除一个节点，然后按顺序将该节点插入已排序列表中，或者扫描原始列表中最大的节点，删除该节点，并在已排序列表中添加该节点。

如果列表很大并且速度很重要，那么自底向上的归并排序要快得多。