Thread: re-order of linked list

Hi,
For a list-linked reorder function. My understanding is the only way to do this is using an algorithm to start at the first node calling the compare funcion and swap the order of nodes as necessary - repeat until each node in the entire list has been compared and swapped. Is this correct or is there a more efficient way of doing this?

Thanks

That is pretty standard. And in most cases this is the most efficient method.

apparently thru reading I found that a temporary head pointer and a variation on the selection sort
would cost about O(N^2) time and very little memory. It should
also involve fewer "swaps" (actually unlinking the selected node
from one list and putting it at one end of the new list).

When referring to a selection sort does this mean the same as the search/find algorithm used in a search function?

Code:

/*

while((current!=NULL)&&(pcl->CompareFPtr(&targetCar,&current->data)!=0))
{
      move to next node

}

then change pointer to new list here

*/

If so I guess would first search to find the smallest data? then link that node to the new list.

Does it sound like am on the right wavelength??

The following code is my attempt of reordering a linked list. I make a tempHead pointer to the list head and set the list head to null I then iterate thru the list to find the smallest node and add to the head of actual list head. I am getting a segmentation fault: core dumped when I use the while(tempHead!=NULL) if I dont use this code only one node is added to the head of list. It may be because I am overiding bounds somewhere when assigning next, not sure.

Any input or suggestions appreciated
Thanks

Code:

/*
void listReorder (List *pcl)
{
       ListNodePtr current,previous,tempHead,smallest;

        tempHead=pcl->head;
        
        pcl->head=NULL;
        current=tempHead;
        smallest=current;
        previous=NULL;
        
        while(tempHead!=NULL)
        {
        	
        	
        		while(current!=NULL&&pcl->CompareFPtr(&smallest->data,&current->data)>0)/*while current not smaller*/
        		{    
        		     previous=current;	
        		     current=current->next;
                                 }/*end while*/
        		
        		 if(previous==NULL)/*unlink smallest node*/
        		{
        			tempHead=current->next;
        			
        		}
        	        else /*unlink smallest node*/
        	        {
        	        	previous->next=current->next;
        	        	
        	        }
        	        
        	       /*add smallest node to the actual head of list*/
        	        smallest=current;
        	        smallest->next=pcl->head;
        	        pcl->head=smallest;
        	        
        	        current=current->next;/*increment current*/
        		
        	
        }/*end while*/
        
  }
*/