Sort a linked list using insertion sort.
题意：用插入排序的方法排序一个链表。
思路：
重启一个头结点指向新链表。
遍历待排序的链表，对每个带排序的节点a，在新链表中找第一个比a大的节点b。
-
将a插入到新链表，需要借助一个辅助指针pre。
public ListNode insertionSortList(ListNode head) { if (head == null) { return null; } ListNode newHead = new ListNode(0); ListNode node = head; while (node != null) { ListNode newNode = new ListNode(node.val); if (newHead.next == null) { newHead.next = newNode; } else { //find first bigger ListNode pre = newHead; ListNode dummy = newHead.next; while (dummy != null && dummy.val < node.val) { pre = pre.next; dummy = dummy.next; } //insert pre.next = newNode; newNode.next = dummy; } node = node.next; } return newHead.next; }
