Reversing a linked list

Given a linked list .Reverse it

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

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


Approach 1:


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 .That is the successor node of a node now point to this node. and the next of this node.


def reverse(self,head):
if head ==None or return head
tail_node= reverse(
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):
for node in 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):   prev=curr   curr=next_ return prev

Time: O(n)

Space: O(1)