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