Problem

Given a linked list, reverse the order of the nodes in the list.
Example input:
1 -> 2 -> 3 -> 4 -> 5
Example output:
5 -> 4 -> 3 -> 2 -> 1

Solution

# Solution:
# The optimal solution is to use a stack to store the nodes in reverse order.
# This is optimal because it uses O(n) space and O(n) time.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def reverse(self):
        stack = []
        current = self.head
        while current:
            stack.append(current)
            current = current.next
        self.head = stack.pop()
        current = self.head
        while stack:
            current.next = stack.pop()
            current = current.next
        current.next = None

    def print_list(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

ll = LinkedList()
ll.head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4 )
fifth = Node(5)
ll.head.next = second
second.next = third
third.next = fourth
fourth.next = fifth

ll.print_list()
print("\n")
ll.reverse()
ll.print_list()