1. ## 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.
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 2. 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. 3. 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  4. 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. 5. 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 6. Iterative:
Code:
```void split( struct node *list, struct node **even, struct node **odd )
{
struct node *next;

for( ; list; list = next )
{
next = list->next;

if( list->data % 2 == 0 )
{
list->next = *even;
*even = list;
}
else
{
list->next = *odd;
*odd = list;
}
}
}```

Quzah. 7. 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.  Popular pages Recent additions 