Sorting Linked Lists (code not concept)

I am a little new at this (notice the name :D )

I created a linked list and want to sort it (notice thread name :p )

Here is my linked list:

Code:

---

struct NODE
{
        int data;

        NODE *next;
                               
};

class LINKED_LIST
{
        public:
                LINKED_LIST();
                ~LINKED_LIST();
                void insertAfterHead(int);       
                int getHead() { return head->data; }
                int getTail() { return tail->data; }
                int printList();
                bool searchList(int);
                void clear();       
                void removeNode(int);
                NODE *head;
                NODE *tail;
};

---

Here is my sorting method:

Code:

---

LINKED_LIST sortList(LINKED_LIST List)
{
        LINKED_LIST Temp;
        NODE *walker = new NODE, *temp_node = new NODE;
        int a = 0,b = 0;
        walker = List.head;
        temp_node->data = 1;

        while(walker != NULL)
        {
                if(walker->data > temp_node->data)
                        temp_node = walker;
                walker = walker->next;
                if(walker->next == NULL)
                {
                        Temp.insertAfterHead(temp_node->data);
                        delete temp_node;
                        walker = List.head;
                        NODE *temp_node = new NODE;
                        temp_node->data = 1;
                }
        }
        return List;
}

---

And I have double checked it and didn't see anything wrong with it, but I make many mistakes in debugging and no idea what is wrong, perhaps some help can be offered :rolleyes:

If you could post the exact behaviour of your sorting algorithm that would be helpful so we know exactly what's going wrong.

The function has quite a few problems. Most notable are the fact that releasing the memory for temp_node destroys the structure of List and will cause future searches to fail with an access violation, an off by one error due to advancing walker before testing walker->next against null, returning the destroyed List instead of the sorted Temp, and memory leaks due to allocating memory for the first test using temp_node, but no release before reassigning the pointer to a node within the list.

The following fixes all but the memory leak.

Code:

---

LINKED_LIST sortList(LINKED_LIST List)
{
  LINKED_LIST Temp;
  NODE *walker, *temp_node = new NODE;
  walker = List.head;
  temp_node->data = 0;

  while(walker != NULL)
  {
    if(walker->data > temp_node->data)
      temp_node = walker;
    if(walker->next == NULL)
    {
      Temp.insertAfterHead(temp_node->data);
      List.removeNode(temp_node->data);
      walker = List.head;
      temp_node = new NODE;
      temp_node->data = 0;
    }
    walker = walker->next;
  }

  return Temp;
}

---