Question

The idea of InsertSort is to sort the data by inserting a value to already sorted data. Our textbook introduced InsertSort for arraylist. Now please write code (psudeocode is fine) to implement InsertSort to sort data from small to large for a Linked LIst. Note that it is NOT doubly linked list. Your code should have the O(n) complexity in the best case

/**definition for singly linked list

* public class ListNode {

* int val;

* LIstNode next;

* LIstNode(int x) {val = x;}

* }

*/

public class Solution {

public ListNode insertionSortList(ListNode head) {

}

}

Answer 1

public ListNode insertionSortList(ListNode head) {
       {
           ListNode sorted = null;
           ListNode current = head;
           while (current != null)
           {
               ListNode next = current.next;
               sortedInsert(current, sorted);
               current = next;
           }
           head = sorted;
           return head;
       }
   }

   private void sortedInsert(ListNode newnode, ListNode sorted)
   {
       if (sorted == null || sorted.val >= newnode.val)
       {
           newnode.next = sorted;
           sorted = newnode;
       }
       else
       {
           ListNode current = sorted;
           while (current.next != null && current.next.val < newnode.val)
           {
               current = current.next;
           }
           newnode.next = current.next;
           current.next = newnode;
       }
   }