制作一个使用指针进行排序的高效算法

Question

考虑一个简单的结构：

struct Node{
 int val;
 Node *next;
 Node *freeNode;
};

现在，我必须只使用freeNode对给定的链表进行排序，并且该方法必须高效。我无法制作另一个列表并在其中使用某种排序插入。也不能使用基因组或气泡排序。列表中任何元素的指针freeNode可以指向列表中的任何元素。

现在我提出了两个想法：

1. 使用freeNode创建一个双链表。

   并进行配对比较，即将第i个elem与第(i+1(个elem进行比较。当我发现需要交换两个元素时，我交换它们，然后再次从列表的开头开始。

   该算法将大于O(n((不确定只是猜测(。这需要很多时间。

2. 另一种方法是，我的freeNode指向比它小的elem

   例如，如果我有30->6->14->56>Tail，那么

   56->freeNode->14
   30->freeNode->14
   14->freeNode->6
   6->freeNode->NULL.
   

   但是，这并没有多大帮助，因为当我插入45 or 20时，我必须重新安排我的freeNode指针。再说一遍，这不是一个非常有效的方法。

对此有什么建议吗？如何使用freeNode实现更好、高效的排序方法。伪代码会起作用，实际上我更喜欢它而不是真正的代码。

编辑：不能使用数组、向量或其他任何东西。只是freeNode指针。用任何你想用的方式。将其保持为NULL或使其指向您选择的元素

Answer 1

您可以创建一个二叉树。使用next作为右子指针，使用freeNode作为左子指针。制作应该对根进行排序的第一个节点。然后，将剩下的节点"插入"到新的二进制树中。

编辑：像这样：

你的typedef:

typedef struct Node{
 int val;
 struct Node *next;
 struct Node *freeNode;
} NodeT;

一些定义使此代码更易于阅读：

// Conversions to make this code easier to read.
#define pRight freeNode
#define pLeft  next

递归二叉树插入：

static void BinTreeInsert( NodeT *pRootNode, NodeT *pChildNode );

编辑2：当明确这是家庭作业时，解决方案被删除。搞清楚，伙计！

该解决方案将是O(n log n(最佳/平均情况，但O(n2(最坏情况。。。如果传入列表已排序。

http://en.m.wikipedia.org/wiki/Tree_sort#section_1