チェーンテーブル挿入ソート

/** 

 * 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)||(head->next==NULL)) return head;

        ListNode *res=head;

        head = head->next;

        res->next=NULL;

       

        while(head){

            ListNode *p=res;

            while(p->next && (p->next->val) <= (head->val)){

               p=p->next;

            }

            if((p->val) > (head->val)){                  // 

                ListNode *temp = head->next;

                head->next=p;

                res=head;

                head=temp;

                

            }

            else{                                          // 

            

            ListNode *temp = p->next;

            p->next=head;

            head=head->next;

            p->next->next=temp;

            }

            

            }

        return res;

        }

};