Peace的专栏

) time using constant space complexity.

链表排序，，O(nlgn)的复杂度，应该是归并或者快排，对链表来说归并应该用起来更顺手一些，尤其是对归并的步骤来说，链表这种数据结构真是再合适不过了。这里我用了递归调用来实现归并步骤，效率可能略微低那么一点点，但是代码简洁得不得了哇~~

归并排序是分治思想的典型例子，因此要不断的划分要排序的序列，那就要找中间节点，这一步在链表中又要费一些力气，这里我用了快慢指针来实现。既然要切开链表，就要找到中间节点，然后在这个节点之前把链表截断。这个“截”的动作其实包括两步，一个是保存中间节点的指针，让它作为一个子列的头结点，二就是要把前一个节点的next指针置为NULL。这里我用了让slow指针比fast指针少走一次的办法，让slow指针指向中间节点的前一个节点。

class Solution {public:ListNode *sortList(ListNode *head) {if (NULL == head || NULL == head->next) return head;ListNode *fast = head, *slow = NULL;while (fast != NULL && fast->next != NULL){fast = fast->next->next;if (slow)slow = slow->next;elseslow = head;}ListNode *temp = slow->next;slow->next = NULL;ListNode *left = sortList(head);ListNode *right = sortList(temp);return mergeTwoLists(left,right);}ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {if (l1 == NULL) return l2;if (l2 == NULL) return l1;ListNode *result;if (l1->val <= l2->val){result = l1;result->next = mergeTwoLists(l1->next, l2);}else{result = l2;result->next = mergeTwoLists(l1, l2->next);}return result;}};

怕仍是不能。于是他们比任何人都看的清楚，又比任何人都看的不确切。