没有额外内存的链接列表的逆转 [英] Reversal of link list without extra memory

问题描述

Hello All，



有一个包含n个元素的单链接列表。两个指针指向链接列表的第一个节点。现在的问题是



如果没有分配任何额外的内存，如何反转链接？



请帮忙。



问候，

joy

Hello All,

There is a singly link list with n elements. Two pointers are pointing to the first node of link list.now question is

"How can one reverse the link without allocationg any extra memory?"

Please help.

Regards,
joy

推荐答案

遍历列表并移动指针。

保持对last节点的引用，并将next节点指针复制到临时变量中。然后将next设置为保存last指针值。将last设置为当前节点，然后移动到临时保存的值。当你到达最后，将头部设置为旧的最后一个（现在是第一个）节点。



在纸上尝试，它会更有意义。

Traverse the list and move the pointers.
Keep a reference to the "last" node, and copy the "next" node pointer into a temporary variable. Then set the "next" to the save "last" pointer value. Set the "last" to the current node, and move to the temporary saved value. When you get to the end, set the head to the old last (now first) node.

Try it on paper, it'll make more sense.

没有分配*任何*额外的内存 - 我不认为它可以做（虽然我已经准备好被证明）。



非常轻量级的方法

1.获取指针（c ++）/对象引用（c＃）第一个元素

2.在项目后移动元素在步骤1中（不要将此指针移动到列表的开头） - 如何执行此操作取决于您使用的语言。

3.重复步骤2直到没有项目后在步骤1中创建的指针。



这将在步骤1中以指针/对象引用的小成本反转列表。





修正了错误的算法

Without allocating *any* extra memory - I don't think it can be done (though I'm prepared to be disproven).

A very lightweight way to do
1. Get a pointer (c++) / object reference (c#) the first element
2. Move the element after the item in step 1 (don't move this pointer) to the start of the list - how to do this depends on the language you are using.
3. Repeat step 2 until there are no items after the pointer created in step 1.

This will reverse the list at the small cost of the pointer/object reference in step 1.


Fixed incorrect algorithm

这篇关于没有额外内存的链接列表的逆转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！