Spread the post

Reverse a linked list using recursion

Write an efficient algorithm to reverse a linked list using recursion. In previous post we are reverse a given linked list iterative manner. Now this one using recursion.

For example given linked list are contain following nodes.

root_ptr12345678

Result

Fuction to Reverse linked list nodes.

Note that if we are reverse a linked list using recursion only need is a one extra pointer.

View pointers and nodes of Linked list.

Stack Areamainroot(pointer) Heap Areastruct Nodedata (int)= 8next (pointer) struct Nodedata (int)= 7next (pointer) struct Nodedata (int)= 6next (pointer) struct Nodedata (int)= 5next (pointer) struct Nodedata (int)= 4next (pointer) struct Nodedata (int)= 3next (pointer) struct Nodedata (int)= 2next (pointer) struct Nodedata (int)= 1next (pointer)= NULL

After reverse.

root_ptr 87654321

Note that change node link.

Stack Areamainroot(pointer) Heap Areastruct Nodedata (int)= 8next (pointer)= NULLstruct Nodedata (int)= 7next (pointer) struct Nodedata (int)= 6next (pointer) struct Nodedata (int)= 5next (pointer) struct Nodedata (int)= 4next (pointer) struct Nodedata (int)= 3next (pointer) struct Nodedata (int)= 2next (pointer) struct Nodedata (int)= 1next (pointer)

Try it Yourself

Program to reverse a singly linked list using recursion. Time complexity O(n).


Output

View process

Stack Areamainroot(pointer)reverseroot(pointer)temp(pointer)reverseroot(pointer)temp(pointer)reverseroot(pointer)temp(pointer)reverseroot(pointer)temp(pointer)reverseroot(pointer)temp(pointer)reverseroot(pointer)temp(pointer)reverseroot(pointer)temp(pointer) Heap Areastruct Nodedata (int)= 8next (pointer) struct Nodedata (int)= 7next (pointer) struct Nodedata (int)= 6next (pointer) struct Nodedata (int)= 5next (pointer) struct Nodedata (int)= 4next (pointer) struct Nodedata (int)= 3next (pointer) struct Nodedata (int)= 2next (pointer) struct Nodedata (int)= 1next (pointer)= NULL

Try it Yourself

Spread the post

Recommended Posts: