LeetCode—-Sort List

发布时间:2017-7-1 11:32:22编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode—-Sort List ",主要涉及到LeetCode—-Sort List 方面的内容,对于LeetCode—-Sort List 感兴趣的同学可以参考一下。

LeetCode—-Sort List

Question

Sort a linked list in O(n log n) time using constant space complexity.

Solution

看到对链表的排序,时间复杂度O(n log n),首先想到的就是归并排序。 但是这里其中有两个技巧:

  1. 就是将两个链表分开的时候,用到了fast-slow法,这是在处理链表分治,也就是找中间节点的一种有效方法。
  2. 还有就是merge的过程,也用到了递归的方式。

Code

/** * 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)            return NULL;        if (head->next == NULL)            return head;        ListNode* p1 = head;        ListNode* p2 = head;        ListNode* pre = head;        // fast-slow 法        while (p2 != NULL && p2->next != NULL) {            pre = p1;            p1 = p1->next;            p2 = p2->next->next;        }        pre->next = NULL;        ListNode* L1 = sortList(head);        ListNode* L2 = sortList(p1);        return merge(L1, L2);    };    // merge 链表的方法,也用到了递归    ListNode* merge(ListNode* L1, ListNode* L2) {        if (L1 == NULL)            return L2;        if (L2 == NULL)            return L1;        if (L1->val <= L2->val) {            L1->next = merge(L1->next, L2);            return L1;        } else {            L2->next = merge(L1, L2->next);            return L2;


上一篇:mysql 小知识
下一篇:滑动到底部自动加载下一页内容,手机H5页面

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款