Google Interview Question(Reverse Linked List)

Question:

Reverse the given Linked List

Explanation:

We need to reverse the linked list given by the user, which should be optimal and less time of execution.

For Example:

Linked List [56,23,6,9]

    Result:[9,6,23,56]

Program:

class Node:

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

class LinkedList:

    # Function to initialize head to None
    def __init__(self):
        self.head = None
    # Function to reverse the given linked list

    def reverse(self):
        prev = None
        current = self.head
        while (current is not None):
            next = current.next
            current.next = prev
            prev = current
            current = next
        self.head = prev

        # Function to insert a new node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

        #Fuction for Printing the Linked List
    def printLinkedList(self):
        temp = self.head
        while (temp):
            print(temp.data),
            temp = temp.next

linkedList = LinkedList()
linkedList.push(20)
linkedList.push(4)
linkedList.push(15)
linkedList.push(85)

print("Input Linked List")
linkedList.printLinkedList()
linkedList.reverse()

print("\nReversed Linked List")
linkedList.printLinkedList()