1 /**
 2      * 插入排序的算法比较简单，我看wiki上，当要在已排序列表中插入一个元素时，是从后到前遍历，
 3      * 由于链表只能从前往后遍历，所以我采用从后到前。
 4      * 要注意的地方就是找到位置时，处理链表的元素插入的具体细节
 5      * @param head
 6      * @return
 7      */
 8     public ListNode insertionSortList(ListNode head){
 9         //当链表为空或者只有一个节点的情况
10         if(head == null || head.next == null)
11             return head;
12         
13         ListNode newHead = head;//记录新的链表头
14         ListNode p1 = head, pp1= null, pointer,pPointer = head, temp = null;
15         for( pointer = head.next;pointer!=null;pointer = temp)
16         {
17             pp1 = null;
18             p1 = newHead;
19             while(p1!= pointer && p1.val<=pointer.val)
20             {
21                 pp1 = p1;
22                 p1 = p1.next;
23             }
24             temp = pointer.next;
25             
26             if(pp1 == null)
27             {
28                 pointer.next = p1;
29                 newHead = pointer;
30                 pPointer.next = temp;
31             }else if(p1 != pointer){
32                 pPointer.next = pointer.next;
33                 pp1.next = pointer;
34                 pointer.next = p1;
35             }
36             else
37                 pPointer = pPointer.next;
38             
39         }
40         return newHead;
41     }

优质内容筛选与推荐>>
1、Python基础学习
2、POJ1655 Balancing Act (树的重心)
3、HQL更新语句设置参数
4、ADSL共享上网
5、nio的分散和聚集读写