re-order of linked list

This is a discussion on re-order of linked list within the C Programming forums, part of the General Programming Boards category; Hi, For a list-linked reorder function. My understanding is the only way to do this is using an algorithm to ...

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    24

    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

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    That is pretty standard. And in most cases this is the most efficient method.

  3. #3
    Registered User
    Join Date
    Sep 2002
    Posts
    24
    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??

  4. #4
    Registered User
    Join Date
    Sep 2002
    Posts
    24

    reorder

    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*/
            
      }
    */

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. putting linked list in order
    By mackieinva in forum C Programming
    Replies: 14
    Last Post: 09-25-2007, 02:26 AM
  3. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  5. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 08:11 AM

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