Sort a linked list using insertion sort.
鏈表的插入排序，其實有2種特殊情況：
1、插入的值插入到已排序的末尾。
leetcode并查集，2、插入的值插入到已排序的最前端。
主要設置了3個指針。
1、pStart是已排序鏈表的開始位置。
2、pInsert是待插入的位置。
LEETCODE。3、pEnd是下一個等待排序的位置。
key：每個已排序的鏈表最后的Node的next指針為null。這樣可以防止循環鏈表，已得不到正確值。
public class Solution {
???? public ListNode insertionSortList(ListNode head) {
??????? if(head == null||head.next == null)return head;
??????? ListNode pStart = head;
??????? ListNode pInsert = head.next;
??????? pStart.next = null;
??????? ListNode pEnd = head;
??????? while(pInsert != null)
??????? {
??????????? pEnd = pInsert.next;
??????????? pStart = sort(pStart,pInsert);
??????????? pInsert = pEnd;
??????? }
??????? head = pStart;
??????? return head;
??? }
???
??? public ListNode sort(ListNode head,ListNode insert)
??? {
??????? ListNode start = head;
??????? ListNode pStr = head;
??????? if(head == null)return head;
??????? while(start.val < insert.val && start.next != null)
??????? {
??????????? pStr = start;
??????????? start = start.next;
??????? }
??????? if(start.val >= insert.val && start == head)
??????? {
??????????? insert.next = head;
??????????? head = insert;
??????? }
??????? else if(start.val >= insert.val)
??????? {
??????????? pStr.next = insert;
??????????? insert.next = start;
??????? }
??????? else if(start.next == null)
??????? {
??????????? start.next = insert;
??????????? insert.next = null;
??????? }
??????? return head;
??? }
}
