title: How to implement Insertion Sorting on a Linked List String Alphabetically
body: <p>I haven't found any information on this, how can I implement insertion sorting on a string with Linked Lists. I have been able to create the Linked List however I cannot figure out how to implement the sorting part.</p>
  <p>I also want to be able to sort by first name and last name but first I need to figure out how to sort by the first name...</p>
  <p>Here is what I have reached so far.</p>
  <pre><code>public class LinkedlistIS
      {
          public CustomerNode head;
          public CustomerNode sorted;
  
          public class CustomerNode
          {
              public int val;
              public string firstName;
              public string lastName;
              public CustomerNode next;
  
              public CustomerNode(int val, string firstName, string lastName)
              {
                  this.val = val;
                  this.firstName = firstName;
                  this.lastName = lastName;
              }
  
              public string FirstName
              {
                  get { return firstName; }
              }
  
              public string LastName
              {
                  get { return lastName; }
              }
  
              public int CompareTo2(CustomerNode another)
              {
                  if (this.lastName.CompareTo(another.LastName) &lt; 0)
                      return -1;
                  else
                      if (this.lastName.CompareTo(another.LastName) == 0)
                      return this.firstName.CompareTo(another.FirstName);
                  else
                      return 1;
              }
  
          }
  
          public void push(int val, string firstName, string lastName)
          {
              /* allocate node */
              CustomerNode newnode = new CustomerNode(val, firstName, lastName);
              val = 1;
  
              /* link the old list off the new node */
              newnode.next = head;
  
              /* move the head to point to the new node */
              head = newnode;
          }
  
  
          // function to sort a singly 
          // linked list using insertion sort
          public void insertionSort(CustomerNode headref)
          {
              // Initialize sorted linked list
              sorted = null;
              CustomerNode current = headref;
  
              // Traverse the given 
              // linked list and insert every
              // node to sorted
              while (current != null)
              {
                  // Store next for next iteration
                  CustomerNode next = current.next;
  
                  // insert current in sorted linked list
                  sortedInsert(current);
  
                  // Update current
                  current = next;
              }
  
              // Update head_ref to point to sorted linked list
              head = sorted;
          }
  
          /*
          * function to insert a new_node in a list. Note that 
          * this function expects a pointer to head_ref as this
          * can modify the head of the input linked list 
          * (similar to push())
          */
          public void sortedInsert(CustomerNode newnode)
          {
              /* Special case for the head end */
              if (sorted == null || sorted.val &gt;= newnode.val)
              {
                  newnode.next = sorted;
                  sorted = newnode;
              }
              else
              {
                  CustomerNode current = sorted;
  
                  /* Locate the node before the point of insertion */
                  while (current.next != null &amp;&amp;
                          current.next.val &lt; newnode.val)
                  {
                      current = current.next;
                  }
                  newnode.next = current.next;
                  current.next = newnode;
              }
          }
  
          /* Function to print linked list */
          public void printlist(CustomerNode head)
          {
              while (head != null)
              {
                  Console.Write(head.firstName + &quot; &quot; + head.lastName + &quot; &quot; + head.val + &quot; &quot;);
                  head = head.next;
              }
          }
  </code></pre>
  <p>Any help would be greatly appreciated.</p>
  <p>Thanks</p>