python 以相反顺序存储链表元素的伪代码

slwdgvem 于 2023-03-11 发布在 Python

关注(0)|答案(2)|浏览(136)

我正在研究一个算法，将一个单向链表的元素以相反的顺序存储在一个数组中。我的导师建议用下面的伪代码来解决这个问题--教室里的每个人都不愿意检查（星期五下午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

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

python

来源：https://stackoverflow.com/questions/75696884/pseudocode-to-store-the-elements-of-a-linked-list-in-reverse-order

2条答案

按热度按时间

xqkwcwgp1#

反对票促使我直接做了一个桌面检查- 22行与官方修复：将节点重置为等于头节点，这使得算法能够存储与数组相反的节点值。

赞(0）回复(0）举报 2023-03-11

vpfxa7rd2#

您的教师忘记在第一个循环结束时将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()

赞(0）回复(0）举报 2023-03-11

我来回答

python 以相反顺序存储链表元素的伪代码

2条答案

相关问题

热门标签

最新问答