Leetcode 147

思路总结

1.在头部搞一个哨兵dummy，处理头部插入的情况。最后返回哨兵的next即可。

2. 搞一个指针，从前往后走，依次比较该node与node.next的值，只要<=,往后走。一旦node.val>node.next.val，则停止在这个位置。此时需要为node.next找到一个合适的插入位置。

3. 再搞一个指针，从dummy.next.val开始与node.next.val比，只要<=，则往后走。而一旦遇到>，说明找到了插入的位置P。

4.在P位置插入即可。这时候就是一个插入节点的问题，处理好指针的指向关系即可。

package Leet_Code;/** * @program: Leetcode * @description: * @create: 2018-09-16 11:37 **/public class Num147_InsertionSortList {    public static class ListNode{        int val;        ListNode next;        ListNode(int x){ val = x;}    }    public static ListNode insertionSortList(ListNode head) {        if(head==null || head.next==null)return head;        ListNode dummy = new ListNode(0);        dummy.next = head;        while (head!=null && head.next !=null){            if(head.val <= head.next.val){                head = head.next;            }            else {                ListNode cur = dummy;                while (cur.next.val < head.next.val){                    cur = cur.next;                }                ListNode temp_head_next = head.next;                ListNode temp_cur_next = cur.next;                cur.next = head.next;                head.next = head.next.next;                temp_head_next.next = temp_cur_next;            }        }        return dummy.next;    }    public static void main(String[] args) {        ListNode head = new ListNode(1);        head.next = new ListNode(8);        head.next.next = new ListNode(2);        head.next.next.next = new ListNode(7);        ListNode cur = insertionSortList(head);        while (cur!=null){            System.out.print(cur.val+"    ");            cur = cur.next;        }    }}