链表排序问题

148. Sort List（链表归并排序）
Sort a linked list in O(n log n) time using constant space complexity.

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(head==NULL||head->next==NULL)
          return head;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next!=NULL&&fast->next->next!=NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* list = slow->next;
        slow->next = NULL;
        head = sortList(head);
        list = sortList(list);
        return merge(head,list);    
    }
    ListNode *merge(ListNode* list1,ListNode* list2)
    {
        if(list1==NULL)
          return list2;
        if(list2==NULL)
          return list1;
        ListNode* newhead = new ListNode(-1);
        ListNode* last = newhead;
        while(list1&&list2)
        {
            if(list1->val < list2->val)
            {
                last->next = list1;
                list1 = list1->next;
            }
            else
            {
                last->next = list2;
                list2 = list2->next;
            }
            last = last->next;
        }
        if(list1==NULL)
           last->next = list2;
        else if(list2==NULL)
           last->next = list1;
        return newhead->next;
    }
};

147.Insertion Sort List（链表插入排序）
Sort a linked list using insertion sort.

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* sortedhead = new ListNode(-1);
        while(head!=NULL)
        {
            ListNode* temp = head->next;
            ListNode* cur = sortedhead;
            while(cur->next!=NULL&&cur->next->val<head->val)
            {
                cur = cur->next;
            }
            head->next = cur->next;
            cur->next = head;
            head = temp;
        }
        return sortedhead->next;
    }
};