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),布布扣,bubuko.com

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

原文：http://blog.csdn.net/thyftguhfyguj/article/details/20158415