C++ Linked Lists Sorting

[andreas.petrou.967]

I have write this program,how to sort the numbers?

// ddd.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>

using namespace std;

struct nodeType
{
    int data;
    nodeType *link;
};

nodeType *head;



int main()
{
    //
    // Init the list
    //
    nodeType *first;
    nodeType *last;
    nodeType *newNode;
    int num;

    first = NULL;
    last = NULL;

    //
    // Build the list the forward approach
    //
    for (int i=0; i<5; i++)
    {
        cout << "Enter number :";
        cin >> num;
        newNode = new nodeType;         
        newNode->data = num;           
        newNode->link = NULL;           
        if (first == NULL)              
        {                               
            first = newNode;
            last = newNode;
        }
        else                            
        {                               
            last->link = newNode;       
            last = newNode;
        }
    }
    //
    // Display the list
    //



    system("PAUSE");
    return(0);
}

[Banfa]

There are all sorts of algorithms you can use, the problem with sorting a singley linked list is in removing an item from the centre of the list requires that you have a pointer to the the item before the item you want to remove (because it has a pointer that needs updating) and that is not easy to come by unless you have remebered it as you scan down the list.

For a short list an easy way to do this is just to remove items from the front of your original list and build them into a new list but putting the in the right order as you build the list rather than just always adding at the beginning or end. This is not too hard but it is also not the most efficient sorting algorithm so you wouldn't want to do it for a very large list.

You could do a bubble sort, this just compares adjacent items and if they are in the wrong order swaps them and keeps going until there is nothing to swap. If you are going to do this given the simplicity of your data (a single int) rather than swapping the items in the list you could swap the values in the items

if (current->data > current->next->data)
{
    int temp = current->data;
    current->data = current->next->data;
    current->next->data = temp;
}

Although some might consider this cheating and it doesn't really scale well to more complex data types.

Swapping items is more complex

if (current->data > current->next->data)
{
    previous = getPreviousItemInList(current);

    previous->next = current->next;
    current->next = current->next->next;
    previous->next->next = current;
}

The first line of the if block, getpreviousIteminList is the issue. Obviously you also need to add in a number of edge cases for when you are at the star or end of the list

[andreas.petrou.967]

Thanks;)