splitting linked list recursive vs. iterative

This is a discussion on splitting linked list recursive vs. iterative within the C Programming forums, part of the General Programming Boards category; Hi, I found interesting function to split linked list in half into two sublist. here's recursive implementation: Code: node * ...

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712

    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

  2. #2
    High Flyer stumpster123's Avatar
    Join Date
    Mar 2005
    Posts
    26
    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. #3
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Quote 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. #4
    High Flyer stumpster123's Avatar
    Join Date
    Mar 2005
    Posts
    26
    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. #5
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    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. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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;
            }
        }
    }
    Yeah, that looks about right.

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    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

  8. #8
    High Flyer stumpster123's Avatar
    Join Date
    Mar 2005
    Posts
    26
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 11:03 AM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  3. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  4. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 11:03 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21