播放gif之继承webView工具类
Sort List
Sort a linked list in O(n log n) time using constant space complexity.
本题好像使用quicksort是不能AC的,只能使用归并排序了。
之前觉得是很困难的题目。
训练了这么久算法,功力终于上升了。虽然还没达化境,但是以前觉得什么归并排序,快速排序好像很难,曾经死记过,始终没有记住,一直都觉得很困惑,怎么才能写出这些算法出来。如今,随时都能写出这样算法来了。而且代码基本上都很工整,清晰的,O(∩_∩)O~
原来算法是练出来的,不是死记硬背的。
我说的化境,是觉得有一天会无论什么难题都可以轻松利用学过的算法,转化成优雅的代码,那时候所有算法都已经融会贯通了,所有题目差不多是一样的,所有算法也是差不多的。呵呵。
struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode *sortList(ListNode *head) { if (!head || !head->next) return head; ListNode *slow = head; ListNode *fast = head->next; while (fast->next) { slow = slow->next; fast = fast->next; if (fast->next) fast = fast->next; } ListNode *h2 = slow->next; slow->next = NULL; head = sortList(head); h2 = sortList(h2); head = combinTwoList(head, h2); return head; } ListNode *combinTwoList(ListNode *n1, ListNode *n2) { ListNode dummy(0); dummy.next = n1; ListNode *pre = &dummy; while (pre->next && n2) { if (pre->next->val > n2->val) { ListNode *t = n2->next; n2->next = pre->next; pre->next = n2; pre = n2; n2 = t; } else pre = pre->next; } if (n2) pre->next = n2; return dummy.next; } };
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。