Given a linked list .Reverse it

input : 1->2->3->null

output: 2->2->1->null

Solution

Approach 1:

Recursive

We create a recursive function to get the tail, which is the new head of our linked list. And for all the node except the last node we do head.next.next=head .That is the successor node of a node now point to this node. and the next of this node.

Psedocode

`def reverse(self,head):   if head ==None or head.next==None: return head   tail_node= reverse(head.next)   head.next.next=head   head.next=None   return tail_node`

The function reverses and returns the new head node (which was the tail node initially).

Time: O(n)

Space: O(n)

n=number of nodes

Approach 2:

Using a hashmap

Here we keep a record of next node of a node and the node itself, using a hashmap. Then we iterate through the hashmap to reverse the linkedlist.

Pseudo code

`def reverse(self,head):   record=dict()   record[head:None]   while(head.next):    record[head.next]=head     head=head.next   for node in record    node.next=record[node]   return head`

Time: O(n)

Space: O(n)

Approach 3:

More optimized Solution

Using 3 pointers namely the previous, current, and next pointers.

Here we keep track of the all three pointers mentioned above, with reversing on the go using a loop

`def reverse(self, head): prev=None curr=head next_=head while(next_!=None):   next_=curr.next   curr.next=prev   prev=curr   curr=next_ return prev`

Time: O(n)

Space: O(1)