147. Insertion Sort List

Sort a linked list using insertion sort.

此题需要设置四个ListNode，第一个是pre，第二个是dummy，第三个是cur，第四个是next；其中插入排序就是说每次从表头开始遍历，当遍历到pre的next的val大于cur的val的时候，把cur插在pre和pre.next之间，next的作用是把带排序的元素头cur的next赋值给next，以便每次都可以让cur遍历下去。代码如下：

/**

 * 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) {

        ListNode dummy = new ListNode(0);

        ListNode cur = head;

        ListNode pre = dummy;

        ListNode next = null;

        while(cur!=null){

            next = cur.next;

            while(pre.next!=null&&pre.next.val<cur.val){

                pre = pre.next;

            }

            cur.next = pre.next;

            pre.next = cur;

            pre = dummy;

            cur = next;

        }

        return dummy.next;

    }

}

147. Insertion Sort List

原文：http://www.cnblogs.com/codeskiller/p/6361034.html