相关疑难解决方法(0)

我能想到的一种方法是反转列表然后阅读它.但这涉及改变不好的清单.
或者我可以复制列表然后将其反转,但这会使用额外的O(n)内存.有没有更好的方法不使用额外的内存,不修改列表并在O(n)时间运行

反向链表代码在c#中是这样的

Void Reverse (Node head)
{
    Node prev= null;
    Node current = head;
    Node nextNode = null;

        while (current!=null)
        {
            nextNode = current.Next;
            current.Next = prev;
            prev=current;
            current = nextNode; 

        }
        head = prev;

}   

递归解决方案是

void ReadBackWard (Node n)
{
    if (n==null)
        return;
    else
        ReadBackward(n.Next);

    Console.WriteLine(n.Data);

}

在对这个答案的评论中提出了一个想法,即反转简单链接列表只能在O(nlog(n))中完成,而不是在O(n)时间内完成.

这绝对是错误的 - O(n)反转不是问题 - 只需遍历列表并随时更改指针.需要三个临时指针 - 这是不变的额外内存.

我完全理解O(nlog(n))比O(n)更差(更慢).

但出于好奇 - 可能是一个用于反转简单链表的O(nlog(n))算法？具有恒定额外存储器的算法是优选的.