LeetCode_Insertion Sort List

题目：Sort a linked list using insertion sort，即仿照插入排序（直接插入排序）对一个链表排序。

插入排序的思想：总共进行n-1趟排序，在排列第i个元素时，前面的i个元素是有序的，将第i个元素插入到前i个元素中，并且保证被插入的数组是有序的，数组是顺序存储的，因此向有序的数组插入一个元素时，需要从插入位置之后的各个元素后移。这就是插入排序的思想。插入排序的时间复杂度O（n^2），是稳定的排序方法。链表并不是顺序存储，因此，再将第i个节点插入到前i个节点，并保证有序时，需要指针的复杂运算。

要判断一次插入是否是插入到链表的最前方，因为这样会有head指针的变化。插入时，需要找到插入位置，且找到插入位置的前驱节点，找到并且找到待插节点的前驱。这个题目本身不难，但是花了好长时间，终于AC，思路值得记下来，也许到了用的上的时候就写不出来了，常看看。。。。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
         if(head == NULL) return NULL;
         if(head->next==NULL) return head;
        // ListNode *p = head;
         ListNode *q = head->next;
         while(q!=NULL)
         {
              ListNode *f = head;
              while(f!=q)
              {
                   if(q->val < f->val)
                   {
                             ListNode *qf = f;
                             while(qf->next!=q)
                             {
                                 qf = qf->next;
                             }//找到q的前驱节点
                             if(f==head)
                             {
                             head = q;
                             qf->next = q->next;
                             q->next = f; 
                             q = qf->next;
                             }
                             else
                             {
                             ListNode *p = head;
                             while(p->next!=f)
                             {
                             p = p->next;
                             }//找到待插入节点的前驱
                             qf->next = q->next;
                             q->next = f; 
                             p->next = q;
                             q = qf->next;
                             }
                             break;
                   }
                   else 
                   {
                        f = f->next;
                   }
              }
              if(f==q)
              q=q->next;
         }
         return head;
    }
};