Thread: splitting linked list recursive vs. iterative

Hi, I found interesting function to split linked list in half into two sublist.
here's recursive implementation:

Code:

node * split(node * list)
{
	node * right;

	if ((list == NULL) || (list->next == NULL))
		return NULL;

    right = list->next;
	list->next = right->next;
	right->next = split(list->next);

	return right;
}

Now, I tried to conert this implementation to iterative function and I figured out this

Code:

node* split_list(node* list)
{
	node* right = NULL;/* right sublist*/
	node* right_it;/* iterator through right list*/
	node* list_it;/* list iterator, list will become left sublist*/

	if (list == NULL)/* if there is no list return NULL*/
	{
		return right;
	}

	if (list->next  != NULL)/* right points to second element in the original list*/
	{
		right = list->next;
		list->next = right->next;
	}
	/* initialize iterators*/
	list_it = list->next;
	right_it = right;

	while (1)
	{
		/* list_it->next points to element which goes to right sublist*/
		right_it->next = list_it->next;
		/*update right iterator*/
		right_it = right_it->next;
		/* update left sublist*/
		list_it->next = right_it->next;
		list_it = list_it->next;
		/* exit (base) case*/
		if ((list_it == NULL) || (list_it->next == NULL))
		{
			right_it->next = NULL;
			break;
		}
	}
	return right;/* return right sublist*/
}

And this works (at least I believe so).
Maybe it could be done more elegant.
It was not a trivial job for me and it took me some ( and lot of seg. faults) time to figure this out.
Recently I implemented iterative functions for tree traversal and it was hard job (for me) too.
What I concluded is that converting from recursive to iterative is a hard work.
What is your experience?
Is there any formal technique or general rules how to approach this problem?
Do you have any advices regarding this example or in general?

Thanks very much

If you want the simpliest way to split a linked list in half without worry about runtime is to simply count how many nodes are in the list. This can be done with a simple for loop say.

Code:

for(i = 0; pTemp != NULL; i++)
{pTemp = pTemp->next;}

then divide that number by 2 and using another for loop proceed to the node in that position. save the node its next is pointing to and then set it to null and return the new lists beginning node. That is the simpliest way it can be done in my view.

Originally Posted by stumpster123

If you want the simpliest way to split a linked list in half without worry about runtime is to simply count how many nodes are in the list. This can be done with a simple for loop say.

Code:

for(i = 0; pTemp != NULL; i++)
{pTemp = pTemp->next;}

then divide that number by 2 and using another for loop proceed to the node in that position. save the node its next is pointing to and then set it to null and return the new lists beginning node. That is the simpliest way it can be done in my view.

Yes, but in that case results would differ from recursive implementation.

As you can see I convert recursive implementation to iterative.
Whole idea is to achive same result with iteration instead recursion

Ok i see sorry i read the initial question wrong. You want to break the list in half where the even nodes go into on sublist and the odd go into another. This can be done like this

Code:

for(i = 0; pTemp != NULL; i++)
{
     if(i%2 == 0)/*Even Node*/
         Put in Right List
     else/*Odd Node*/
         Put in Left List
    pTemp = pTemp->next;
}

If i am still reading this wrong then tell me but if im not then this should work.

Ok, that is basically a good idea, however I'd like you to try to write function with this prototype

Code:

 
node* split(node*) ;

In which you use:

Code:

  if(i%2 == 0)/*Even Node*/
         Put in Right List
     else/*Odd Node*/
         Put in Left List

My initial task was to convert recursive function to iterative function, but never mind I'm interested how you would implement your idea in code.
Cheers

Thank you master quzah, but I wanted to see how he could handle this. I post prototype hoping he'll ask to change it to

Code:

node* split(node** list);

or the way you suggested it.
So return is right (left) sublist, while list become left (right) sublist.
I hope he would do this to reward him with good start rep points, but anyway thanks.
How about my question about experience with converting recursion to iteration?

Cheers

Micko

lol got back to the post too slow otherwise I would have posted it. Don't worry i can do it but quzah beat me to the punch.