98-链表排序
思路
采用归并排序（时间复杂度是O(nlogn)的排序有快速排序、归并排序、堆排序），使用快慢指针找出链表中点。
code
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: You should return the head of the sorted linked list,
using constant space complexity.
*/
ListNode *sortList(ListNode *head) {
// write your code here
if(head == NULL || head->next == NULL) {
return head;
}
ListNode *fast = head, *slow = head, *temp = head;;
while(fast != NULL && fast->next != NULL) {
temp = slow;
slow = slow->next;
fast = fast->next->next;
}
temp->next = NULL;
return mergeList(sortList(head), sortList(slow));
}
ListNode *mergeList(ListNode *head1, ListNode *head2) {
if(head1 == NULL) {
return head2;
}
if(head2 == NULL) {
return head1;
}
ListNode newHead(0);
ListNode *temp = &newHead;
while(head1 != NULL && head2 != NULL) {
if(head1->val < head2->val) {
temp->next = head1;
head1 = head1->next;
}
else {
temp->next = head2;
head2 = head2->next;
}
temp = temp->next;
}
if(head1 != NULL) {
temp->next = head1;
}
else if(head2 != NULL) {
temp->next = head2;
}
return newHead.next;
}
};