Thread: Reverse a list in recursion

Hello i'm trying to reverse a list using recursion i thought of a solution but there is one part of the solution i do not like,hoping i can get some ideas for it.

Code:

Node *rev(Node *head)
{
	Node *res, *tmp;
	if (head->next == NULL)
	{
/*g is a global variable to save the new head,any ideas on how i can save the head without using a global variable?*/
		g = head;
		return head;
	}
	tmp = head;
	res = rev(head->next);
	res->next = tmp;
	tmp->next = NULL;
	return tmp;
}

I have solved it , i would still be glad to hear other opinions on the matter.

Code:

Node *rev(Node *head)
{
	Node *res,*ptr;
	if (head->next == NULL)
	{		
		return head;
	}
	
	res = rev(head->next);
	ptr = res;
	head->next = NULL;
	while (ptr->next != NULL)
	{
		ptr = ptr->next;
	}
	ptr->next = head;
	return res;
}

Can you keep track from both ends? That seems like it would be a lot faster.

Originally Posted by CodeSlapper

Can you keep track from both ends? That seems like it would be a lot faster.

Sorry I don't understand what you mean, perhaps clarify ?

If you kept track of the tail and head pointer, you might be able to walk the list and swap the tail and head pointer. It might cut down on the complexity and number of operations.

First go, swap head and tail, move both ptrs to the next one and keep going till they are both NULL. You might have to account for the when you have an even and odd number of elements if you do this.

I'd make a helper function that takes the original list and the reversed list as parameters. Inside the helper function, if the original list has any elements in it, move the head from the original list to the head of the reversed list, and then call the helper function again from itself.

Code:

Node *rev_helper(Node *list, Node *reversed)
{
    if (list) {
        Node *next = list->next;
        list->next = reversed;
        return rev_helper(next, list);
    }
    return reversed;
}

Node *rev(Node *list)
{
    return rev_helper(list, NULL);
}

Untested.