本文主要是介绍Crack LeetCode 之 148. Sort List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://leetcode.com/problems/sort-list/
对于链表的排序，非常适合用归并排序算法。但本题还要求只用O(1)的内存空间；如果考虑归并算法的栈的话，实际上本题的解法使用的是O(n)的内存空间。所以本题解法的时间复杂度是O(n Log(n))，空间复杂度是O(n)。其实归并排序也可以使用遍历的方法实现，每次遍历使用不同的步长即可，但是本人懒得修改了～～
C++代码如下：
class Solution {
public:ListNode * sortList(ListNode * head) {if(head == NULL || head->next == NULL)return head;ListNode * walker = head;ListNode * runner = head;while(runner->next!=NULL && runner->next->next!=NULL) {walker = walker->next;runner = runner->next->next;}ListNode * head2 = walker->next;walker->next = NULL;ListNode * head1 = head;head1 = sortList(head1);head2 = sortList(head2);return merge(head1, head2);}ListNode * merge(ListNode * head1, ListNode * head2) {ListNode * helper = new ListNode(0);helper->next = head1;ListNode * pre = helper;while(head1!=NULL && head2!=NULL) {if(head1->val<head2->val)head1 = head1->next;else {ListNode * next = head2->next;head2->next = pre->next;pre->next = head2;head2 = next;}pre = pre->next;}if(head2!=NULL)pre->next = head2;return helper->next;}
};
Python代码如下：
class Solution:def sortList(self, head):if head == None or head.next == None:return headwalker = headrunner = headwhile runner.next != None and runner.next.next != None:walker = walker.nextrunner = runner.next.nexthead2 = self.sortList(walker.next)walker.next = Nonehead1 = self.sortList(head)return self.merge(head1, head2)def merge(self, head1, head2):if head1 == None:return head2if head2 == None:return head1helper = ListNode(0)helper.next = head1pre = helperwhile head1 != None and head2 != None:if head1.val < head2.val:head1 = head1.nextelse:next = head2.nexthead2.next = head1pre.next = head2head2 = nextpre = pre.nextif head2 != None:pre.next = head2return helper.next
这篇关于Crack LeetCode 之 148. Sort List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
