//Sort a linked list using insertion sort
//单链表的插入排序
/** * Definition for singly-linked list. * public class ListNode
*{ * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public ListNode insertionSortList(ListNode head)
{
if(head == null || head.next == null)
{
return head;
}
ListNode _newHead = new ListNode(Integer.MIN_VALUE);
ListNode _node = head;
while(_node != null)
{
ListNode _p = _newHead;
//记录_node的下一个节点
ListNode _next = _node.next;
while(_p.next != null && _p.next.val <= _node.val)
{
_p = _p.next;
}
_node.next = _p.next;
_p.next = _node;
_node = _next;
}
return _newHead.next;
}
