题解 | #链表的插入排序#

主要确定的步骤：

1. 需要双重遍历。
2. 对于待插入的结点小于首结点情况，做处理
3. 找到对应插入的结点，进行插入。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode insertionSortList (ListNode head) {
        // write code here
         // write code here
        if (head == null || head.next == null) {
            return head;
        }
      // 永远标记未排序的首个结点
        ListNode pB = head.next;
      // 将原来的head摘干净
        head.next = null;
      // 便利已排序结点的指针
        ListNode pA;
        ListNode tmp;
        while (pB != null) {
          // 每次从头开始
            pA = head;
          // 处理头结点排序情况
            if (pB.val < pA.val) {
                tmp = pB.next;
              // 这里是pA本身
                pB.next = pA;
                head = pB;
                pB = tmp;
            } else {
              // 这里使用的是pA的next结点
                while (pA.next != null && pA.next.val < pB.val) {
                    pA = pA.next;
                }
                tmp = pB.next;
                pB.next = pA.next;
                pA.next = pB;
                pB = tmp;
            }

        }

        return head;
    }
}