【leetcode每日一题】148.sort List

题目：) time using constant space complexity.

解析：题目要求是对链表进行排序，但是复杂度不能超过O(nlgn)。符合题意的常见排序方法有快排、归并排序和堆排序。以下是用归并排序解决此题的步骤。

1）将链表从中间部分分为两个链表。具体做法是：声明两个指针，一个快指针和一个慢指针，当快指针指向NULL时，慢指针指向中间节点。

2）对左右链表进行递归，，直到链表只剩一个节点为止。

3）调用归并函数，对两个链表进行归并。归并函数的实现思路，请见第21题：Merge two sorted lists

代码如下：

/** * 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) {if(head==NULL||head->next==NULL)return head;return mergesort(head);}ListNode *mergesort(ListNode *head){if(head==NULL||head->next==NULL)return head;ListNode *fast=head,*slow=head;ListNode *leftHalf,*rightHalf,*pre;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;pre=slow;slow=slow->next;}pre->next=NULL;leftHalf=mergesort(head);rightHalf=mergesort(slow);return merge(leftHalf,rightHalf);}ListNode *merge(ListNode *leftHalf,ListNode *rightHalf){ListNode *result=new ListNode(0);ListNode *temp=result;while(leftHalf!=NULL&&rightHalf!=NULL){if(leftHalf->val<rightHalf->val){temp->next=leftHalf;temp=temp->next;leftHalf=leftHalf->next;}else{temp->next=rightHalf;temp=temp->next;rightHalf=rightHalf->next;}}if(leftHalf!=NULL)temp->next=leftHalf;if(rightHalf!=NULL)temp->next=rightHalf;temp=result->next;//delete result;return temp;}};

版权声明：本文为博主原创文章，未经博主允许不得转载。

穷则思变，差则思勤！没有比人更高的山没有比脚更长的路。