单链表排序

单链表的排序

http://www.nowcoder.com/questionTerminal/f23604257af94d939848729b1a5cda08

题目描述
给定一个无序单链表,实现单链表的排序(按升序排序)。

解法

    //解法1:归并排序
    // 时间O(NlogN) 空间O(logN)
    ListNode* sortInList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        //二分
        //注意:需要做到:a->b 能断开
        //ListNode *fast = head, *slow = head;
        ListNode *fast = head->next, *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* left = head;
        ListNode* right = slow->next;
        slow->next = nullptr;
        ListNode* sortLeft = sortInList(left);
        ListNode* sortRight = sortInList(right);

        //合
        ListNode* ans = merge(sortLeft, sortRight);
        return ans;
    }

    ListNode* merge(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr || l2 == nullptr) return l1? l1:l2;
        ListNode dummy(0);
        ListNode* cur = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                cur = cur->next;
                l1 = l1->next;
            } else {
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }
        }
        if (l1) cur->next = l1;
        if (l2) cur->next = l2;
        return dummy.next;
    }
全部评论

相关推荐

03-04 19:02
云南大学 Java
Yki_:没挂,只是没人捞,该干啥干啥,等着就好了
点赞 评论 收藏
分享
01-24 12:50
门头沟学院 C++
投票
菜狗二号:还有啥想的 指定国有行啊,去了就开始幸福美满的生活了,选华子不是折腾自己么,最终财富积累度是差不多的,但是幸福指数是相差甚远的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务