Insertion Sort List

对链表进行插入排序，比对数组排序麻烦一点。

ListNode *insertSortList(ListNode *head)

      {

          ListNode dummy(-);

          for (ListNode *cur = head; cur != nullptr;)

          {

              //将当前结点插入到此结点之后

              auto Pos = findPos(&dummy, cur->val);

              //保存当前结点的下一个结点

              ListNode *temp = cur->next;

              //插入

              cur->next = Pos->next;

              Pos->next = cur;

              //继续下一个结点

              cur = temp;

          }

      }

      ListNode *findPos(ListNode *head, int val)

      {

          ListNode *pre = nullptr;

          for (ListNode *cur = head; cur != nullptr&&cur->val <= val; pre = cur, cur = cur->next);

          return pre;

      }