0

考虑一个简单的结构：

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

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

现在我想出了两个想法：

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

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

    该算法将超过 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 或让它指向您选择的元素。

4

1 回答 1

2

你可以制作一棵二叉树。使用 next 作为你的右子指针和 freeNode 作为你的左子指针。使您应该对根进行排序的第一个节点。然后，取出其余节点并将它们“插入”到新的二叉树中。

编辑：像这样：

你的类型定义：

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

于 2013-02-27T07:10:29.950 回答