SortList 单链表排序要求复杂度O(NlgN)

题目:Sort a linked list in O(n log n) time using constant space complexity.

leetcode上的一道题，觉得还不错，写的比较多的插入排序O(N^2),不满足题目的要求，排序的算法主要参考归并排序，首先求出单链表的长度，对单链表进行划分，递归分别处理左半边和右半边，最后进行merge，和归并的算法实一样的，就是链表处理起来要注意点!

#include <iostream>
using namespace std;

struct ListNode {
     int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
};
 
void createList(ListNode *&head){
 int x;
 ListNode *r;
 while(cin >> x && x!=-1){
  ListNode *p = new ListNode(x);
  if(head == NULL)
   head = p;
  else
   r->next = p;
  r = p;
 }
}

void print(ListNode *p){
 while(p){
  cout << p->val << " ";
  p = p->next;
 }
 cout << endl;
}

class Solution {
public:
    ListNode *sortList(ListNode *head) {
     int len = getLen(head);
     return sortLt(head,len);
    }

    ListNode *sortLt(ListNode *head,int len){
     if(len <= 1)
      return head;
     ListNode *head1,*head2;
     head1 = head2 = NULL;
     int len1,len2;
     divide(head,len,head1,len1,head2,len2);
     head1 = sortLt(head1,len1);
     head2 = sortLt(head2,len2);
     return mergeList(head1,head2);
    }


    void divide(ListNode *head,int len,ListNode *&head1,
     int &len1,ListNode *&head2,int &len2){
     len1 = len / 2;
     len2 = len - len1;
     head1 = head;
     ListNode *tp = head;
     for(int i = 1;i < len1;i++){
      tp = tp->next;
     }
     head2 = tp -> next;
     tp->next = NULL; 
    }

    ListNode *mergeList(ListNode * head1,ListNode * head2){
     ListNode *L = new ListNode(-1);
     ListNode *pre = L;
     while(head1 && head2){
      if(head1->val < head2->val){
       pre->next = head1;
       head1 = head1->next;
      }else{
       pre->next= head2;
       head2 = head2->next;
      }
      pre = pre->next;
     }
     if(head1)
      pre->next = head1;
     if(head2)
      pre->next = head2;
     return L->next;
    }

    int getLen(ListNode *head){
     int len = 0;
     while(head != NULL){
      len++;
      head = head->next;
     }
     return len;
    }

};

int main(int argc, char const *argv[])
{
 ListNode *head = NULL;
 createList(head);
 print(head);
 Solution s;
 ListNode *rt = s.sortList(head);
 print(rt);
 return 0;
}

SortList 单链表排序 要求复杂度O(NlgN)

SortList 单链表排序要求复杂度O(NlgN)