c++ - 按升序对链表进行排序C++

所以我有一个单链表。新项目将添加到链的最前面，因此，如果添加8,4,10，则列表将为10,4,8。无论如何，现在我试图在插入完成后对列表进行排序，只是我无法弄清楚如何依次遍历这些数字并按升序重新排列它们。我可能会在这里稍事休息，然后再回来，希望能帮助我解决这个问题。

*这是一个用于学校的项目，因此建议我使用其他容器对我的情况没有帮助，除非提供信息，因为我无法更改正在使用的内容。

列表的布局

struct Node
    {
      int Item;      // User data item
      Node * Succ;   // Link to the node's successor
    };

unsigned Num //number of items in the list
Node * Head //pointer to the first node

我的插入功能看起来像这样

Node * newOne;
newOne = new (nothrow) Node;
newOne->Item = X;
newOne->Succ = NULL;

if(Head == NULL)
{
        Head = newOne;
}
else
{
        newOne->Succ = Head;
        Head = newOne;
}
Num++;

最佳答案

这可以通过两种方式完成，我不会发布代码，但希望这会对您有所帮助。

1.插入时按升序排列

这涉及始终按升序添加元素。例如，如果链接列表是

            | 1  |

然后添加5，新的链接列表为

           |1|--->|5|

如果再加上3，它应该是

           |1| ---> |3| ----> |5|

这涉及比较新元素，直到找到正确的位置。

2.等待所有元素插入，然后按升序排列。

这将涉及在链接列表的元素上使用排序算法，例如合并排序，插入排序，冒泡排序等。

在对数字进行排序之后，以正确的顺序重写链接列表。

例：

如果链接列表包含

        3 2 5 1 6

经过算法排序

  1 2 3 5 6 (stored in an array)

现在循环浏览链接列表，并以正确的顺序替换元素。

如果节点包含其他元素，则要小心，这些其他元素也需要替换。

注意：这需要额外的内存，另一种方法是交换节点，这将花费更长的时间。除非链接列表包含大量节点（因此使内存变得重要）或具有其他元素，否则使用数组会更简单。

关于c++ - 按升序对链表进行排序C++，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13402453/