Reversing a linked list

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)