每日一题2-对链表进行插入排序

  对链表进行插入排序

/**
 * https://www.lintcode.com/problem/insertion-sort-list/
 *
 *  **/

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The head of linked list.
     */
    ListNode * insertionSortList(ListNode * head) {
        //插入排序
        if(head ==NULL ||head->next ==NULL)
        {   
            //少于一个节点不需要排序
           return head ;
        }
        //01 构造带头节点的单链表，默认第一个节点有序

        ListNode start(0);//保持头节点不变是为了插入方面，也可以不要，每次寻找pre节点时候 判断一下是否null
        start.next=head;

        ListNode* end=head; //有序链表结束位置，end也是遍历的迭代器  
        ListNode* pre=NULL;//辅助变量  
        ListNode* temp=NULL;//辅助变量  
        /** 初始状态
         *   input：7--6--5--4--3 -2 -1 
         *   
         *  start.next---7--6--5--4--3 -2 -1 
         *      |        |  |             
         *      |        |  temp
         *      |        end
         *      Pre
         */

        //遍历剩余 未排序的
        while(end)
        {
            temp=end->next;

            if(end->next ==NULL ||temp->val>end->val)
            {
               end=end->next;
          /** 最后一个元素
         *   input：7--6--5--4--3 -2 -1 
         *   
         *  start.next---1-2--3--4--5 -6 -7----NUll
         *                                |       |             
         *                                |       temp 
         *                                end(end没有改变过一次，end=null 结束循环)
         *      
         */
            }else

        /** 第一次排序
         *   input：7--6--5--4--3 -2 -1 
         *   
         *   before：
         *   start.next---7--6--5--4--3 -2 -1 
         *      |        |  |             
         *      |        |  temp
         *      |        end
         *      Pre
         * 
         * after：
         * start.next---6----7---5--4--3 -2 -1 
         *      |       |    |              
         *      |       |    |  
         *      |       temp end
         *      Pre
         * 
         */ 
         {
               pre=&start;
              while(pre->next &&pre->next->val < temp->val)
              {
                pre=pre->next;//pre插入位置前一个元素  pre->7

              }
              //插入元素 pre -6-7-5

              end->next=temp->next; //7---5
              temp->next=pre->next;//6---7
              pre->next=temp;//start

        }
      }
        return start.next;

    }
};

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
         //基本合法检查，还不涉及排序过程
        if(head == NULL || head->next == NULL) {
            return head;
        }

        //01 依赖空间 
        ListNode first(0); //有序链表头开始部分，固定头节点位置，保证插入节点元素 pre节点一定存在。
        first.next=head; //第一默认有序  head->6->5->1->8
        ListNode* cur = head; // 有序链表头结束部分

        ListNode* pre = NULL;//插入排序需要插入记录位置，每次都需要重新计算

        //从第一个元素开始遍历链表，假设第一个元素是有序的
        while(cur) {
            //满足条件 1-8
            if(cur->next &&cur->next->val <cur->val)
            {
             //寻找插入位置  .
             pre=&first;//从有序链表head开始遍历.次数，pre 指向head节点，没有数据
             while(cur->next&&pre->next && cur->next->val>pre->next->val) // head->6->5->1->8
             {
                pre=pre->next;//pre->next 就是插入地方。pre是前面一个节点。存在插入规则，是在固定节点后面插入
             }
          // pre  <temp < pre-next

            //插入过程 类似节点翻转最前面位置（pre->next 就是插入地方）
            ListNode* temp = cur->next; //记录待插入元素5，head->6->5->1
            cur->next=temp->next; //移除待插入元素5 ，移动下一个元素 head->6->1
            temp->next =pre->next;//待插入元素5后面节点。 
                                  //                    5  ->6->1    
                                  //                   head->6->1 

            pre->next=temp;//待插入元素5前面节点。 head->5->6->1
            //这里不需要一定cur=cur->next，移动下一个元素 head->6->1 完成
            }else
            {
                 cur=cur->next;//移动下一个元素
            }             
        }

        return first.next;
    }

};