Tip:
Highlight text to annotate it
X
in our previous lesson we saw how we can traverse
a linked list using recursion we wrote code
to print the elements of linked list in forward as well as reverse order
using recursion we did not actually reverse the list
we just printed the elements in reverse order now in this lesson we will
reverse
a linked list using recursion and this is yet
another famous programming interview question so if we have
an input list like this we have linked list of integers here
we have four nodes in the linked list
each rectangular block here with two partitions is a Node first field is
to store the data and another to store the address of the
next node the second field stores the address of the next node
and of course we will have one variable to store the
address of the First node or head node we name that variable head
we may name it anything i have named it head so this is our
input list and after reversal our output should be
like this, this variable head should store the address of
the last node in the original list, the last node in the original list
was at address 250 and we will go like from 250 to 150, 150 to 200
200 to 100 and 100 to null, null is nothing but
address zero
we have already seen how we can reverse a linked list
using iterative method in one of our previous lessons
let us now see how we can solve this problem using recursion
in our solution we must reverse the list by
adjusting the links by reversing the links
not by moving around data or something so let us first understand the logic
that we can use
in our recursive approach if you remember from our previous lesson
where we had used recursion to print the list backward
print the elements in reverse order then recursion gives us a Way
to traverse the list backward in our C or C++ program.Programatically
Node will be a structure like this so let's first look at the
function from the previous lesson the recursive function that
was used to print the list backward to this function we passed the address of
a Node
initially we pass the address of the head Node and we have this
exit condition if the address passed is null
then we simply return else we make a recursive call and Pass the address of the
next
Node so main method will typically call Reverseprint passing it the address of
the head node and this guy will first make a recursive call and then
when this recursive call finishes then only it will
print so I'm writing RP as shortcut for ReversePrint
so the recursion will go on like this and when it reaches this particular call when
argument is null it will return so this call will finish and again the control will
come
to this call with address 250 as argument
and now we're printing the value
of the node at address 250 which will be four
and then this guy finishes and then we go ahead and print five
and similarly we then go on to print six and two
so recursion kind of gives us a way to first
traverse the list in the forward direction and then
traverse the list in the backward direction so let us now see how we can
implement reverse function using recursion
let's say for the sake of simplicity in implementation that
head is a global variable so it is accessible to all the functions
now we will implement a function named reverse that will take
the address of a node as argument initially we will pass
address of the head node to this function now I want to do something like
this in my recursion I want to
go on till the end, I want to go on
making a recursive call till i reach the last node, for the last node
the link part will be null so this is my exit condition from recursion
on this exit condition is what will stop us from going on infinitely in a
recursion and what I'm doing here is something very simple
as soon as I'm reaching the last node I'm modifying the
head pointer to make it point to this guy so the recursion will work like this
from the main method we will call the Reverse function passing it
the address of the head node address 100 we will come and check this condition if
P.next is equal to null, no it is equal to 200 for
the node at address 100 so this recursion
will go on till we reach this call,
call to Reverse passing it address 250
and now we will come down and now we have come to this exit condition and now
head will be set as P and the list will look like this
and now Reverse(250), the call to Reverse(250) will finish and we will come back to
Reverse(150)
their is no statement here after
this recursive call to Reverse function if there were some statements here
then they would have executed now for Reverse(150) after we would have come
from Reverse(250)
and that's how we actually traverse the list in
reverse order if you see when Reverse(250)
has finished the Node till
250 is already reversed because head is pointing to this node and the link part of
this node
is set as null so till 250 we are already reversed
now when we come to 150 we can make sure the
list is reversed till 150 when we finish the execution of Reverse(150)
to do that we can write statement like this
we will have to do two things we will have to cut this node and make this
cut point to this guy
so we will build this link and we would have to cut this link
and make this guy point to null and that's how
Node till address 150 will be reversed after we finish this call
so I have written these three lines in my function that will execute
after the recursive call so
they will execute when the the recursion is folding up
and we are traversing the list in the backward direction
so when we are executing Reverse(150)
and we have come back to it after recursion we are at this particular line
so P would be 150 and q
would be P.next so q would be 250 so this guy is
p and this guy is q and we are saying that set q.next is equal to
p so we will set this particular field
as 100 so we are building this link
and cutting this link and now we are saying that set
p.next equal null so we are building this link
making p.next null and now this call to Reverse(150) finishes
and when this call has finished the list
till 150 is reversed as you can see head is 250 so from 250 we will go to
150 and from 150 we are going to null
so till 150 we have a reversed list
so this is how things will look like when the call to Reverse(200) finishes
till 200 we have reversed list
and once again we come to execution of Reverse(100) and this is how things will
look like finally when
Reverse(100) finish we will return back to the main function
we had seen in the previous lesson that
how things will happen in the memory when recursion execute
in recursion we save the state of execution of all the function calls
in stack section of the memory in this function all we're doing is
basically we are storing the addresses of Node in a structure as we go forward
in recursion
and then we first work on the last
Node to make it part of the reverse list and then we once again come back to the
previous node
and we keep doing this, watch the previous lesson for detailed explanation
and simulation of how things will happen in the memory
for recursion
there are couple of more things here one thing is that
instead of writing these two lines I could write one line for these two lines
I could say something like p->next
->next equal p and that would have meant the same
except that this statement is more of skated
and there is one more thing we have assumed that head is a global variable
what if head
is not a global variable this Reverse function will have to
return the address of the modified head I leave that as an exercise for you to do
so this was reversing a linked list using recursion
thanks for watching