Problem: To test both data structure and the recursion concept, a wonderful and confusing interview question asked to experienced people is “Reverse a linked list using recursion”.
Solution:
In recursive approach, we need to move to the end of the node. But must stop just before the end of the node, and we should have total 3 nodes in hand.
head (stack) head->next (not null) head->next->next
head is what is in the stack. head->next->next will always be NULL. If it is not NULL, recursion continues. This is the base condition for our recursion.
Now, we connect head->next->next to head. and set head->next to NULL. since, we have pushed the traversed head’s in the stack.
If there is only one node, there is no need to reverse the list. So, its ok to check for head and head next both being non-NULL are not. If any one of it becomes NULL, we can return the head recorded.
void recursiveReverse(struct node** head_ref) { struct node* first; struct node* rest; /* empty list */ if (*head_ref == NULL) return; first = *head_ref; rest = first->next; /* List has only one node */ if (rest == NULL) return; /* put the first element on the end of the list */ recursiveReverse(&rest); first->next->next = first; /* tricky step */ first->next = NULL; /* fix the head pointer */ *head_ref = rest; }
can u illustrate the above problrm solution with an example
Thank you for the question. I thought about different solution;
Node* reverseList(Node* head, Node* prevNode = NULL)
{
if(head != NULL)
{
Node* temp = head->next ;
head->next = prevNode;
if(temp != NULL)
{
return reverseList(temp, head);
}
}
return head;
}
@ P. Alpagut it returns the head as address of revrsed last node i.e adress of 1st node of normal list . so to print the list again we hav to travrse from end
Can you please compare this with the one you stated above.
Problems: One for sure that is traversing after reversing the list.
Reverse(Start->Next,Start);
Start->Next = null;
Reverse(Node* current, Node* previous)
{
if(current->Next != null)
Reverse(current->Next, current);
current->Next = previous;
}
In java:
private ListElement reverse(ListElement head) {
if (head == null || head.next == null) return head;
ListElement tail = head.next;
head.next = null;
ListElement reversed = reverse(tail);
tail.next = head;
return reversed;
}
Here is another way of it…
void ReverseTheList(Node<T>* ptr)
{
if(ptr->getNext()) {
ReverseTheList(ptr->getNext());
}
else {
mHead = ptr;
return;
}
ptr->getNext()->setNext(ptr);
}
void ReverseTheList()
{
if(mHead) {
Node<T>* t = mHead;
ReverseTheList(mHead);
t->setNext(NULL);
}
}
void reverse(Node *par, Node *next, Node **root){
if(par == NULL){return;}
if(next==NULL){
*root = par;
return;
}
reverse(next,next->next,root);
next->next=par;
par->next=NULL;
}
//no need to traverse from the end
Public ListNode reverseList(ListNode head){
If (head == null) return null;
Return reverseListRecursiveHelper(head, null);
}
Public ListNode reverseListRecursiveHelper(ListNode head, ListNode prevNode){
ListNode nextNode = head.getNext();
head.setNext(prevNode);
If (nextNode == null) return head;
Return reverseListRecursiveHelper(nextNode, head);
}
public static NodeSLL reverseRecursion(NodeSLL ll){
if(ll==null) return ll;
return reverseRecursionHelper(null, ll);
}
private static NodeSLL reverseRecursionHelper(NodeSLL prev,NodeSLL curr){
if(curr==null) return prev;
NodeSLL next = curr.next;
curr.next = prev;
NodeSLL r = reverseRecursionHelper(curr, next);
return r;
}