Reverse A Linked List In Python

#Approach 1: Iterative Approach to Reverse Linked List

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


class Solution:
    def __init__(self):
        self.head = None  # Head of list

    # Returns the linked list in display format
    def __str__(self):
        linked_list_str = ""
        temp = self.head
        while temp:
            linked_list_str = (linked_list_str +
                               str(temp.data) + " ")
            temp = temp.next
        return linked_list_str

    # Pushes new data to the head of the list
    def push(self, data):
        temp = Node(data)
        temp.next = self.head
        self.head = temp

    def reverse_list(self, head):
        previous_node = None
        current_node = head
        while current_node:
            next_node = current_node.next
            current_node.next = previous_node
            previous_node = current_node
            current_node = next_node
        head = previous_node
        return head


# Driver code
linked_list = Solution()
linked_list.push(5)
linked_list.push(4)
linked_list.push(3)
linked_list.push(2)
linked_list.push(1)
print("Given linked list")
print(linked_list)
linked_list.head = linked_list.reverse_list(linked_list.head)
print("Reversed linked list")
print(linked_list)

Test Cases:

# Example 1
linked_list = Solution()
linked_list.push(5)
linked_list.push(4)
linked_list.push(3)
linked_list.push(2)
linked_list.push(1)

Output: 
Given linked list
 1 2 3 4 5 
Reversed linked list
 5 4 3 2 1 

# Example 2
linked_list = Solution()
linked_list.push(5)
linked_list.push(4)
linked_list.push(3)
linked_list.push(2)
linked_list.push(1)

Output: 
Given linked list
 1 2  
Reversed linked list
 2 1

# Example 3
linked_list = Solution()
linked_list.push(None)

Output: 
Given linked list
 None
Reversed linked list
 None 

#Approach 2: Recursive Approach to Reverse Linked List

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


class Solution:
    def __init__(self):
        self.head = None  # Head of list

    # Returns the linked list in display format
    def __str__(self):
        linkedListStr = ""
        temp = self.head
        while temp:
            linkedListStr = (linkedListStr +
                             str(temp.data) + " ")
            temp = temp.next
        return linkedListStr

    # Pushes new data to the head of the list
    def push(self, data):
        temp = Node(data)
        temp.next = self.head
        self.head = temp

    def reverse_list(self, node, prev=None):
        if not node:
            return prev
        n = node.next
        node.next = prev
        return self.reverse_list(n, node)


# Driver code
linked_list = Solution()
linked_list.push(5)
linked_list.push(4)
linked_list.push(3)
linked_list.push(2)
linked_list.push(1)
print("Given linked list")
print(linked_list)
linked_list.head = linked_list.reverse_list(linked_list.head)

print("Reversed linked list")
print(linked_list)

Test Cases:

# Example 1
linked_list = Solution()
linked_list.push(5)
linked_list.push(4)
linked_list.push(3)
linked_list.push(2)
linked_list.push(1)

Output: 
Given linked list
 1 2 3 4 5 
Reversed linked list
 5 4 3 2 1 

# Example 2
linked_list = Solution()
linked_list.push(5)
linked_list.push(4)
linked_list.push(3)
linked_list.push(2)
linked_list.push(1)

Output: 
Given linked list
 1 2  
Reversed linked list
 2 1

# Example 3
linked_list = Solution()
linked_list.push(None)

Output: 
Given linked list
 None
Reversed linked list
 None