[LintCode] Sort List [分治]

Shisui 发布于2019-08-14 15:32 / 3107人阅读

摘要：这道题目可以用分治法来做，首先从链表中点分割链表，然后将两个链表重新排序并合并。

Problem

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

Example

Given 1-3->2->null, sort it to 1->2->3->null.

Note

这道题目可以用分治法来做，首先从链表中点分割链表，然后将两个链表重新排序并合并。

Solution

public class Solution {
    public ListNode sortList(ListNode head) {  
        if (head == null || head.next == null) return head;
        ListNode mid = findMid(head);
        ListNode n2 = sortList(mid.next);
        mid.next = null;
        ListNode n1 = sortList(head);
        return merge(n1, n2);
    }
    public ListNode findMid(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    public ListNode merge(ListNode n1, ListNode n2) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (n1 != null && n2 != null) {
            if (n1.val < n2.val) {
                head.next = n1;
                n1 = n1.next;
            }
            else {
                head.next = n2;
                n2 = n2.next;
            }
            head = head.next;
        }
        if (n1 != null) head.next = n1;
        else head.next = n2;
        return dummy.next;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65829.html

[LintCode] Merge K Sorted Lists [DC/Heap]

摘要：分治做法中，函数依然是将链表结点两两进行比较，然后在函数中迭代两个二分后的结果。 Problem Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example Given lists: [ 2->4->null, null, ...

happyhuangjinjin 2019-08-14 15:32 评论0 收藏0
[LintCode] Insertion Sort List

摘要：插入排序维基百科一般来说，插入排序都采用在数组上实现。在放这个数之前，这个数的目标位置和原始位置之间的数都要先进行后移。最后，当，即遍历完整个原链表之后，新链表排序完成。 Problem Sort a linked list using insertion sort. Example Given 1->3->2->0->null, return 0->1->2->3->null. No...

wzyplus 2019-08-14 15:21 评论0 收藏0
LintCode547/548_求数组交集不同解法小结

摘要：求数组交集不同解法小结声明文章均为本人技术笔记，转载请注明出处求数组交集要求元素不重复，给出两个数组，求二者交集且元素不重复，查找会超时解法一排序二分查找算法超时主要发生在大数组查找过程，因此采用二分查找提升查找效率，交集用保存实现去重解法 LintCode547/548_求数组交集不同解法小结 [TOC] 声明文章均为本人技术笔记，转载请注明出处：[1] https://segme...

gxyz 2019-08-16 10:34 评论0 收藏0
[LeetCode/LintCode] Merge Intervals

摘要：方法上没太多难点，先按所有区间的起点排序，然后用和两个指针，如果有交集进行操作，否则向后移动。由于要求的，就对原数组直接进行操作了。时间复杂度是的时间。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...

gougoujiang 2019-08-14 15:16 评论0 收藏0
[Lintcode] Find Peak Element 找峰值

摘要：找出该矩阵的一个峰值元素，返回他的坐标原题链接一维二分搜索复杂度时间空间思路最直观的方法是遍历整个矩阵，但这要的时间。 Find Peak Element I A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], fi...

leiyi 2019-08-14 12:24 评论0 收藏0