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

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

record=dict()
for node in record
node.next=record[node]

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