17
08/2015
[LeetCode] Sort List
Sort List
Sort a linked list in O(n log n) time using constant space complexity.解题思路：
题意为以常量存储空间和O(nlogn)时间复杂度来排序链表。
可以用合并排序法，并用双指针法来找到中间节点。
产生一个头结点方便编码。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode* myHead = new ListNode(0);
myHead->next = head;
myHead = mergeSort(myHead);
head = myHead->next;
delete myHead;
return head;
}
ListNode* mergeSort(ListNode* head){
if(head->next==NULL || head->next->next==NULL){
return head;
}
ListNode* one = head, *two = head;
while(two->next!=NULL && two->next->next!=NULL){
one = one->next;
two = two->next->next;
}
two = new ListNode(0);
two->next = one->next;
one->next = NULL;
one = mergeSort(head);
two = mergeSort(two);
one = merge(one, two);
return one;
}
ListNode* merge(ListNode* head1, ListNode* head2){
ListNode* head = new ListNode(0);
ListNode* tail = head;
while(head1->next!=NULL && head2->next!=NULL){
if(head1->next->val > head2->next->val){
tail->next = head2->next;
head2->next = head2->next->next;
}else{
tail->next = head1->next;
head1->next = head1->next->next;
}
tail = tail->next;
}
if(head1->next!=NULL){
tail->next = head1->next;
}
if(head2->next!=NULL){
tail->next = head2->next;
}
delete head1;
delete head2;
return head;
}
};转载请注明：康瑞部落 » [LeetCode] Sort List
0 条评论