Given a linked list .Reverse it
input : 1->2->3->null
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.
if head ==None or head.next==None: return head tail_node= reverse(head.next)
head.next=None return tail_node
The function reverses and returns the new head node (which was the tail node initially).
n=number of nodes
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.
for node in record
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