pseudocode to store the elements of a linked list in reverse order

Question

I am working on an algorithm to store the elements of a singly linked list in reverse order inside an array. my tutor suggested the following pseudocode for the problem - everyone in the classroom was reluctant to check (4 pm on a Friday) and copied it straight away but I was the one who was giving him the eye because something just didn't sit right with it, to which he smiled. He told me to come up with my own implementation for this method before everyone left as a homework just for myself. Here is the pseudocode he gave out to the class:

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;

I still haven't figured out why the pseudocode does not work as intended - the only plausible answer that I come up with when I did a small desk check was that the loop does not break when it reaches None, but I still haven't pin-point the exact issue - can somebody please point me to the right direction? what is wrong with this pseudocode and why is it not working as intended?

Since I was curious - I stayed in the classroom for an hour and try to think of a solution. I have then come up with the coded solution to reverse the order of the linked list in 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

I have yet to deduce why the pseudocode does not work as intended.

Answer 1

Your teacher forgot to reset the node counter to head at the end of the first loop:

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

Also since you return a list, the space complexity is O(n). In that case it is quite a shame to have an O(n²) time complexity (your teacher's algorithm). Yours is much better since it has an O(n) time complexity (depending on the implementation of insert(0, x)). To be sure, you could do this:

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