1 package com.lw.leet5; 2  3 /** 4  * @ClassName:Solution 5  * @Description: 6  *         Insertion Sort List  7  *         Sort a linked list using insertion sort. 8  * @Author LiuWei 9  * @Date 2014年8月20日下午7:50:0710  * @Mail nashiyue1314@163.com 11  */12 public class Solution {13 14     public ListNode insertionSortList(ListNode head) {15         // if only one or two elements ,return head16         if(head == null || head.next == null){17             return head;18         }19         ListNode cur = head.next;20         ListNode tmp = null;21         while(cur != null){22             tmp = head;23             //get the insertion position24             while(tmp != cur && tmp.val < cur.val){25                 tmp = tmp.next;26             }27             //if need insert, switch the value28             if(tmp != cur){29                 int num1 = cur.val;30                 int num2 ;31                 while(tmp != cur){32                     //store the tmp value33                     num2 = tmp.val;34                     tmp.val = num1;35                     num1 = num2;36                     tmp = tmp.next;37                 }38                 //init cur39                 tmp.val = num1;40             }41             cur = cur.next;42         }43         return head;44     }45 46     public static void main(String args[]) {47         int[] arr = {10,3,2,4,0,0,-1,2,-2};48          ListNode head = new ListNode(arr[0]);49          ListNode curr = head;50          for(int i=1; i<arr.length; i++){51              ListNode node = new ListNode(arr[i]);52              curr.next = node;53              curr = curr.next;54          }55         56         ListNode tmp  = new Solution().insertionSortList(head);57         while(tmp != null){58             System.out.println(tmp.val);59             tmp = tmp.next;60         }61     }62 63 }