Insertion Sort List

    由于排序后头节点不一定，故需要引入 dummy 大法，并以此节点的作为最后返回结果的头节点，返回的链表从dummy->next这里开始构建。首先我们每次都从dummy->next开始遍历，依次和上一轮处理到的节点的值进行比较，直至找到不小于上一轮节点值的节点为止，随后将上一轮节点插入到当前遍历的节点之前，依此类推。文字描述起来可能比较模糊，大家可以结合以下的代码在纸上分析下。

    1. """
    2. Definition of ListNode
    3. class ListNode(object):
    5.     def __init__(self, val, next=None):
    6.         self.val = val
    7.         self.next = next
    8. """
    9. class Solution:
    10.     """
    11.     @param head: The first node of linked list.
    12.     @return: The head of linked list.
    13.     """
    14.     def insertionSortList(self, head):
    15.         dummy = ListNode(0)
    16.         cur = head
    17.         while cur is not None:
    18.             pre = dummy
    19.             while pre.next is not None and pre.next.val < cur.val:
    20.                 pre = pre.next
    21.             temp = cur.next
    22.             cur.next = pre.next
    23.             pre.next = cur
    24.         return dummy.next

    C++

    Java

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) { val = x; }
    7.  * }
    8.  */
    9. public class Solution {
    10.     public ListNode insertionSortList(ListNode head) {
    11.         ListNode dummy = new ListNode(0);
    13.         while (cur != null) {
    14.             ListNode pre = dummy;
    15.             while (pre.next != null && pre.next.val < cur.val) {
    16.                 pre = pre.next;
    17.             }
    18.             ListNode temp = cur.next;
    19.             cur.next = pre.next;
    20.             pre.next = cur;
    21.             cur = temp;
    22.         }
    24.         return dummy.next;
    25.     }
    26. }
    1. 新建 dummy 节点，用以处理最终返回结果中头节点不定的情况。
    2. 以cur表示当前正在处理的节点，在从 dummy 开始遍历前保存cur的下一个节点作为下一轮的cur.
    3. 以pre作为遍历节点，直到找到不小于cur值的节点为止。
    4. 将pre的下一个节点pre->next链接到cur->next上，cur链接到pre->next, 最后将cur指向下一个节点。
    5. 返回dummy->next最为最终头节点。

    Python 的实现在 lintcode 上会提示 TLE, leetcode 上勉强通过，这里需要注意的是采用if A is not None:的效率要比if A:高，不然 leetcode 上也过不了。具体原因可参考 Stack Overflow 上的讨论。

    复杂度分析

    最坏情况：原链表正好逆序，由于是单向链表只能从前往后依次遍历，交换和比较次数均为 1/2 O(n^2), 总的时间复杂度近似为 O(n^2), 空间复杂度同上，近似为 O(1).

    从题解1的复杂度分析可以看出其在最好情况下时间复杂度都为 O(n^2) ，这显然是需要优化的。 仔细观察可发现最好情况下的比较次数 是可以优化到 O(n) 的。思路自然就是先判断链表是否有序，仅对降序的部分进行处理。优化之后的代码就没题解1那么容易写对了，建议画个图自行纸上分析下。

    Python

    1. /**
    2.  * Definition of ListNode
    3.  * class ListNode {
    4.  * public:
    5.  *     int val;
    6.  *     ListNode *next;
    7.  *     ListNode(int val) {
    8.  *         this->next = NULL;
    9.  *     }
    11.  */
    12. class Solution {
    13. public:
    14.     /**
    15.      * @param head: The first node of linked list.
    16.      * @return: The head of linked list.
    17.      */
    18.     ListNode *insertionSortList(ListNode *head) {
    19.         ListNode *dummy = new ListNode(0);
    20.         dummy->next = head;
    21.     ListNode *cur = head;
    22.         while (cur != NULL) {
    23.             if (cur->next != NULL && cur->next->val < cur->val) {
    24.                 ListNode *pre = dummy;
    25.                 // find insert position for smaller(cur->next)
    26.                 while (pre->next != NULL && pre->next->val <= cur->next->val) {
    27.                     pre = pre->next;
    28.                 }
    29.                 // insert cur->next after pre
    30.                 ListNode *temp = pre->next;
    31.                 pre->next = cur->next;
    32.                 cur->next = cur->next->next;
    33.                 pre->next->next = temp;
    34.             } else {
    35.                 cur = cur->next;
    36.             }
    37.         }
    39.         return dummy->next;
    40.     }
    41. };

    Java

    源码分析

    1. 新建 dummy 节点并将其next 指向head
    2. 分情况讨论，仅需要处理逆序部分。
    3. 由于已经确认链表逆序，故仅需将较小值(cur->next而不是cur)的节点插入到链表的合适位置。
    4. 将cur->next插入到pre之后，这里需要四个步骤，需要特别小心！

    如上图所示，将cur->next插入到节点后大致分为3个步骤。

    最好情况下时间复杂度降至 O(n), 其他同题解1.