title: Stable Quicksort With Linked List
body: <p>I am trying to make a stable implementation of quicksort using linked lists, and for some reason this code is crashing. It seems to get to the second iteration of the while loop in partition before it crashes.</p>
  
  <p>Basically, I'm using the head as a pivot point and anything less goes in a new linked list and anything greater than the pivot goes in a new linked list as well. This is called recursively and then at the end they are combined.</p>
  
  <pre><code>    class Node
      {
      public:
          Node* next;
          int key;
          int key2;
  
          Node()
          {
              next = NULL;
          }
      };
  
      void fillRandom(Node*&amp; root, int length)
      {
         if(length != 0){
              root-&gt;key = rand()%10;
              root-&gt;next = new Node;
              fillRandom(root-&gt;next, length-1);
          }
      }
  
      void partitionLL(Node*&amp; lessThan, Node*&amp; greaterThan, Node*&amp; root)
      {
          Node* lessThanTemp = lessThan; Node* greaterThanTemp = greaterThan;
          Node* temp = root;
  
          while(temp-&gt;next != NULL)
          {
              if(temp-&gt;key &gt; root-&gt;key){
                  greaterThanTemp = temp;
                  greaterThanTemp-&gt;next = new Node;
                  greaterThanTemp = greaterThanTemp-&gt;next;
              }else{
                  lessThanTemp = temp;
                  lessThanTemp-&gt;next = new Node;
                  lessThanTemp = lessThanTemp-&gt;next;
              }
              temp = temp-&gt;next;
          }
      }
  
      void quickSort(Node* root)
      {
          if(root-&gt;next != NULL){//i.e. theres only two nodes in the list
              Node* lessThan = new Node; Node* greaterThan = new Node;
              partitionLL(lessThan, greaterThan, root);
              quickSort(lessThan);
              quickSort(greaterThan);
          }else{
              return;
          }
      }
  
      int main()
      {
          int length = 15;
          Node* root = new Node;
  
          fillRandom(root, length);
          quickSort(root);
      }
  </code></pre>