以倒序存储链表元素的伪代码

Question

我正在研究一种算法，将单向链表的元素以相反的顺序存储在数组中。我的导师建议使用以下伪代码来解决这个问题——教室里的每个人都不愿意检查（周五下午 4 点）并立即复制它，但我是那个给了他眼睛的人，因为有些东西不合适它，他微笑着。他告诉我在每个人离开之前为这个方法想出我自己的实现作为我自己的家庭作业。这是他给全班的伪代码：

Reverse(head): 
    Result = [] 
    
    Cursor = null; 
    Last_node = null; 
    
    Node = head; 
    
    While (cursor != head): 
        While (node != cursor): 
            Last_node = node; 
            Node = node.next; 
        Cursor = last_node; 
        Result.append(cursor); 
    Return result;

我仍然没有弄清楚为什么伪代码不能按预期工作——当我做一个小的桌面检查时，我想到的唯一合理的答案是循环在达到 None 时不会中断，但我仍然没有'无法确定确切的问题 - 有人可以指出正确的方向吗？这个伪代码有什么问题，为什么它没有按预期工作？

因为好奇——我在教室呆了一个小时，想办法想办法。然后我想出了编码解决方案来反转 python 中链表的顺序：

# reverse the order of the linked list
def reverse(self) -> list:
    result = []
    node = self._front

    while node is not None:
        result.insert(0, node.get_value())
        node = node._next

    return result

我还没有推断出为什么伪代码不能按预期工作。

Answer 1

否决票触发我直接进行桌面检查 - 22 行官方修复：将节点重置为等于头节点。这使得算法能够将节点的值反向存储到数组中。

Answer 2

你的老师忘记在第一个循环结束时将

node

计数器重置为

head

：

def reverse(head): 
    result = []
    cursor = None 
    last_node = None 
    node = head
    while (cursor != head):
        while (node != cursor): 
            last_node = node 
            node = node.next
        # adding this line
        node = head
        cursor = last_node
        result.append(cursor) 
    return result

此外，由于您返回了一个列表，因此空间复杂度为

O(n)

。在那种情况下，具有

O(n²)

时间复杂度（您老师的算法）是非常可耻的。你的要好得多，因为它具有

O(n)

时间复杂度（取决于

insert(0, x)

的实现）。可以肯定的是，你可以这样做：

def reverse2(head):
    result = []
    while(head is not None):
        result.append(head)
        head = head.next
    return result.reverse()