# GOOGLE
"""
    SOLVED -- LEETCODE#206
    Given a singly-linked list, reverse the list. 
    This can be done iteratively or recursively. 
    Can you get both solutions?
    Example:
    Input: 4 -> 3 -> 2 -> 1 -> 0 -> NULL
    Output: 0 -> 1 -> 2 -> 3 -> 4 -> NULL
"""


class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    # Function to print the list
    def printList(self):
        node = self
        output = ''
        while node != None:
            output += str(node.val)
            output += " "
            node = node.next
        print(output)

    # Iterative Solution
    def reverseIteratively(self, head):
        # Time: O(n)     Space: O(1)
        if head.next == None:
            return

        rev = None
        curr = head
        while head != None:
            head = head.next
            curr.next = rev
            rev = curr
            curr = head
        head = rev
        return

    # Recursive Solution
    def reverseRecursively(self, head):
        # Time: O(n)     Space: O(n)
        # see leetcode solution for the case
        # when we return the pointer to the node
        if head.next == None:
            return head

        curr = head
        head = head.next
        curr.next = None
        tail = self.reverseRecursively(head)
        tail.next = curr
        return curr


# Test Program
# Initialize the test list:
testHead = ListNode(4)
node1 = ListNode(3)
testHead.next = node1
node2 = ListNode(2)
node1.next = node2
node3 = ListNode(1)
node2.next = node3
testTail = ListNode(0)
node3.next = testTail

print("Initial list: ")
testHead.printList()
# 4 3 2 1 0
# testHead.reverseIteratively(testHead)
testHead.reverseRecursively(testHead)
print("List after reversal: ")
testTail.printList()
# 0 1 2 3 4
