一、题目

　　1、审题

　　

　　2、分析

　　　　给出一个链表，采用插入排序的方式将节点进行排序。

 

二、解答

　　1、思路：

　　　　方法一、

　　　　　　①、将第一个节点结点作为新的有序链表的开始。指针 node 指向 head， next 指向 head 的下一个元素。

　　　　　　②、将 next 值依次与 node 所指链表节点进行比较，并插入合适位置。

　　　　　　③、next 依次向后移动，直到所有节点全部插入 node 所指链表，即 next 为 空。

public ListNode insertionSortList(ListNode head) {        if(head == null)            return head;                ListNode node = head;        ListNode next = head.next;        node.next = null;                while(next != null) {            ListNode pre = node;            ListNode cur = node.next;            // next 值比头节点还小            if(pre.val >= next.val) {                ListNode tmp = next.next;                next.next = pre;                node = next;                next = tmp;            }            // next 值比头结点大，找到合适位置插入            else {                while(cur  != null && cur.val < next.val) {                    pre = cur;                    cur = cur.next;                }                pre.next = next;                next = next.next;                pre.next.next = cur;            }        }        return head;    }

 

　　　　方法二、

　　　　　　新建一个头节点，在头结点中依次插入预原 List 中的节点。　

public ListNode insertionSortList(ListNode head) {        if(head == null)            return head;                ListNode helper = new ListNode(0);        ListNode cur = head;        ListNode pre = helper;        ListNode next = null;                while(cur != null) {            next = cur.next;            //find the right place to insert            while(pre.next != null && pre.next.val < cur.val)                 pre = pre.next;                        //insert between pre and pre.next            cur.next = pre.next;            pre.next = cur;            pre = helper;            cur = next;        }        return helper.next;    }