@@ -0,0 +1,1586 @@
+/*%0ASort a linked list using insertion sort.%0A*/%0A%0A%0Aimport java.io.*;%0Aimport java.util.*;%0A%0Apublic class InsertionSortList %7B%0A%09public static class ListNode %7B%0A%09%09int val;%0A%09%09ListNode next;%0A%09%09public ListNode(int x) %7B val = x; %7D%0A%09%7D%0A%0A%09public static ListNode insertionSortList(ListNode head) %7B%0A%09%09if(head == null) return null;%0A%09%09ListNode res = new ListNode(Integer.MIN_VALUE);%0A%09%09res.next = head;%0A%09%09ListNode cur = res;%0A%09%09while(cur!= null && cur.next != null)%7B%0A%09%09%09if(cur.next.val %3C cur.val)%7B%0A%09%09%09%09ListNode temp = cur.next;%0A%09%09%09%09cur.next = cur.next.next;%0A%09%09%09%09findNode(res, temp);%0A%09%09%09%7Delse%7B%0A%09%09%09%09cur = cur.next;%0A%09%09%09%7D%0A%09%09%7D%0A%09%09return res.next;%0A%09%7D%0A%0A%09public static void findNode(ListNode res, ListNode cur)%7B%0A%09%09while(res.next!= null && cur.val %3E res.next.val)%7B%0A%09%09%09res = res.next;%0A%09%09%7D%0A%09%09ListNode t = res.next;%0A%09%09res.next = cur;%0A%09%09cur.next = t;%0A%09%09return;%0A%09%7D%0A%0A%09public static void main(String%5B%5D args) %7B%0A%09%09ListNode head = new ListNode(3);%0A%09%09ListNode node2 = new ListNode(1);%0A%09%09ListNode node3 = new ListNode(7);%0A%09%09ListNode node4 = new ListNode(4);%0A%09%09ListNode node5 = new ListNode(9);%0A%09%09ListNode node6 = new ListNode(5);%0A%09%09head.next = node2;%0A%09%09node2.next = node3;%0A%09%09node3.next = node4;%0A%09%09node4.next = node5;%0A%09%09node5.next = node6;%0A%09%09node6.next = null;%0A%09%09System.out.print( %22Before: %22);%0A%09%09ListNode curr = head;%0A%09%09while(curr != null)%7B%0A%09%09%09System.out.print( curr.val + %22 %22);%0A%09%09%09curr = curr.next;%0A%09%09%7D%0A%09    System.out.println(%22%22);%0A%09%09System.out.print(%22After: %22);%0A%09%09ListNode newHead = insertionSortList(head);%0A%09%09curr = newHead;%0A%09%09while(curr != null)%7B%0A%09%09%09System.out.print( curr.val + %22 %22);%0A%09%09%09curr = curr.next;%0A%09%09%7D%0A%09%09return;%0A%09%7D%09%0A%7D%0A

insert sort list