title: Linked list sorting in C
body: <p>I'm writing a simple file for one of my classes that is a simple linked list activity and I need to sort a linked list.</p>
  
  <p>This is my source code so far:</p>
  
  <pre><code>/*
   * Simple list manipulation exercise.
   * 1. Create a list of integers.
   * 2. Print the list.
   * 3. Sort the list.
   * 4. Print the list
   * 5. Free the list nodes.
   */
  
  #include &lt;stdlib.h&gt;
  #include &lt;stdio.h&gt;
  
  struct node {
      int value ;
      struct node *next ;
  } ;
  
  extern struct node *mk_node(int v) ;
  extern void print_list(struct node *head) ;
  extern struct node *sort_list(struct node *head) ;
  extern void free_list(struct node *head) ;
  
  #define NVALUES (6)
  
  int initial_contents[] = { 3, 8, 2, 5, 1, 9 } ;
  
  /*
   * Main driver program. Create the list from the initial_contents,
   * print it, sort it, print it, free it, and return.
   */
  
  int main() {
      struct node *head = NULL ;
      struct node *curp ;
  
      int i ;
  
      /*
       * Put the initial values into the list. This algorithm
       * will result in the values being inserted in reverse
       * order of the array.
       */
      for( i = 0 ; i &lt; NVALUES ; i++ ) {
          curp = mk_node( initial_contents[i] ) ;
          curp-&gt;next = head ;
          head = curp ;
      }
  
      print_list(head) ;
      head = sort_list(head) ;
      print_list(head) ;
      free_list(head) ;
  
      return 0 ;
  }
  
  /*
   * Return a new node with 'v' as the label and a NULL next link.
   */
  
  struct node *mk_node(int v) {
      struct node *newp = malloc( sizeof(struct node) ) ;
      newp-&gt;value = v;
      newp-&gt;next = NULL;  
  
      return newp ; // Place holder
  }
  
  /*
   * Print the list headed by 'head', one value per line.
   */
  
  void print_list(struct node *head) {
      printf("List: ");
      struct node *ptr = head;
      while(ptr!=NULL){
          printf("%d ", ptr-&gt;value);
          ptr=ptr-&gt;next;
      }
      putchar('\n');
  }    
  
  /*
   * Sort the list headed by 'head', returning a pointer to the node
   * that ends up at the head of the list.
   */
  
  struct node *sort_list(struct node *head) {
      struct node *tmpPtr;
      struct node *tmpNxt;
  
      tmpPtr = head;
      tmpNxt = head-&gt;next;
  
      int a, tmp;
  
      while(tmpNxt != NULL){
          a = tmpPtr-&gt;value;
          while(tmpNxt != tmpPtr &amp;&amp; tmpNxt-&gt;value &lt; a){
              tmp = a;
              tmpPtr-&gt;value = tmpNxt-&gt;value;
              tmpNxt-&gt;value = tmp;
              tmpPtr = tmpPtr-&gt;next;
          }
          tmpPtr = head;
          tmpNxt = tmpNxt-&gt;next;
      }
  
      return tmpPtr ; // Place holder
  }
  
  /*
   * Free all the nodes in the list headed by 'head'.
   */
  
  void free_list(struct node *head) {
      //struct node *releasep ;
      //while( head != NULL ){
  //      releasep = head;
  //      head = head-&gt;next ;
  //
  //      free(releasep-&gt;value) ;
  //      free(releasep) ;
  //  }
  }
  </code></pre>
  
  <p>I'm having troubles with my sort method. I even even went step by step and I can't find the problem.</p>
  
  <p>Below is my program's output.</p>
  
  <pre><code>XXXXXXX@linus:~/350/c_memory_activity$ gcc -o test listsort.c 
  XXXXXXX@linus:~/350/c_memory_activity$ ./test 
  List: 9 1 5 2 8 3 
  List: 1 9 5 2 8 3 
  XXXXXXX@linus:~/350/c_memory_activity$ 
  </code></pre>
  
  <p>P.S.: Original sorting algorithm was here: <a href="https://stackoverflow.com/questions/3901341/linked-list-insertion-sort">Linked list insertion sort</a></p>