Sorting a linked list

This is a discussion on Sorting a linked list within the C Programming forums, part of the General Programming Boards category; Over the past couple days, I have been trying all kinds of different methods or rearranging a linked list by ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    15

    Sorting a linked list

    Over the past couple days, I have been trying all kinds of different methods or rearranging a linked list by value. Everytime I though I had it, I would find some order in which the input would cause it not to rearrange properly. My current method seems to work perfect except for 1 small problem. When I increase the value of one of the nodes to the point where it is the biggest number in the list, it just disappears.


    my call to the function is...
    sortList(&head, tempString, curVal);
    where head is the start of the list.

    Code:
    int sortList(ListNodePtr *sPtr, char* string, int value){
        ListNodePtr head;
        ListNodePtr previousPtr;
        ListNodePtr newPtr;
        
        head = *sPtr;
        previousPtr = NULL;
        newPtr = malloc(sizeof(ListNode));  /*create node*/
        if(newPtr != NULL) { /*is space available*/
            newPtr->symbol = strdup(string);    /*set newPtr values to be ready to insert it*/
            newPtr->value = value;
            newPtr->nextPtr = NULL;
    
    
            while(head != NULL) {
                /*if its greater than the first node, 
    insert it at the start. This must be where the issue is, 
    but I used this same code in an earlier section of my program 
    and it correctly inserted the node at the start.*/
                if(value > head->value && previousPtr == NULL) {
                    newPtr->nextPtr = *sPtr;
                    *sPtr = newPtr;
                    break;
                }
                /*put the node between previous and head*/
                else if(value > head->value && previousPtr != NULL) {
                    previousPtr->nextPtr = newPtr;
                    newPtr->nextPtr = head;
                    break;
                }
                else if(head->nextPtr == NULL) {
                    head->nextPtr = newPtr;
                    break;
                }
    
    
                previousPtr = head;   /*move to next node*/
                head = head->nextPtr;
            }
        }
    I am not sure if anyone can understand this since I didnt put very much code up, but since its an assignment I dont want to put it all up. I have mainly been messing around with passing head or &head. Also with using sPtr and *sPtr. I feel like the problem could have something to do with that.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,496
    Next time, more complete code might be helpful, so I can just copy-paste, compile and debug. I worked up a test program around this easily enough though. You should also learn to use a debugger, so you can step through and see exactly what's happening at each step of the program. That's how I solved this. It took me about 30 seconds to find the problem.

    You don't cover the case of inserting int an empty list. That is, if head is NULL, you skip your whole insert loop. You need something like:
    Code:
    if head == NULL
        *sPtr = newPtr
    else
        while (head != NULL)
            // rest of your loop

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help with sorting linked list
    By hockey8 in forum C Programming
    Replies: 1
    Last Post: 11-08-2010, 01:55 PM
  2. Sorting a linked list
    By qtwo in forum C++ Programming
    Replies: 2
    Last Post: 12-20-2009, 10:53 AM
  3. Sorting a Linked List
    By cannsyl in forum C++ Programming
    Replies: 1
    Last Post: 12-03-2008, 06:20 AM
  4. Sorting a linked list
    By thoseion in forum C Programming
    Replies: 6
    Last Post: 11-13-2006, 09:34 AM
  5. Sorting a linked list
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 09-18-2001, 04:49 PM

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