要么改变世界,要么适应世界

非递归方式进行归并排序链表

2020-08-24 20:13:00
145
目录

题目来源:LeetCode 148

题目大意

给你一个链表, 在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

啥?把链表排序,把时间复杂度控制在O(nlogn)?,链表不像数组,排序没有那么方便啊!归并排序,常数级空间复杂度?那只能非递归实现了~~

不过我不知道该怎么写,看了评论区,自己整理了一下。

算法实现

ListNode mergetSort(ListNode head) {
    if (head == null || head.next == null) return head;
    int listLength = 0;
    for (ListNode l = head; l != null; l = l.next) listLength++;
    ListNode helperRoot = new ListNode(0);
    helperRoot.next = head;
    ListNode helper = helperRoot;
    // 步长, 即每个子区间的长度
    int step = 1;
    while (step < listLength) {
        helper = helperRoot;
        for (ListNode start = helperRoot.next; start != null; ) {
            ListNode end = start, mid = start, pre = start;
            int len = 0;
            while (len < step && mid != null) {
                len++;
                pre = mid;
                mid = mid.next;
            }
            pre.next = null;
            end = mid;
            pre = mid;
            len = 0;
            while (len < step && end != null) {
                len++;
                pre = end;
                end = end.next;
            }
            if (pre != null) pre.next = null;
            ListNode nextStart = end;
            ListNode[] merger = merger(start, mid);
            helper.next = merger[0];
            merger[1].next = nextStart;
            start = nextStart;
            helper = merger[1];
        }
        step *= 2;
    }
    return helperRoot.next;
}

// 返回合并后的链表头指针和尾指针
ListNode[] merger(ListNode left, ListNode rightStart) {
    ListNode leftStart = left;
    ListNode listTail = left;
    if (leftStart == null && rightStart == null) return null;
    // 其实在本题中, 左边链表不会是null
    if (leftStart == null) {
        listTail = rightStart;
        while (listTail.next != null) listTail = listTail.next;
        return new ListNode[]{rightStart, listTail};
    }
    if (rightStart == null) {
        while (listTail.next != null) listTail = listTail.next;
        return new ListNode[]{left, listTail};
    }
    ListNode root = new ListNode(0);
    ListNode tail = root;
    while (rightStart != null && leftStart != null) {
        if (leftStart.val < rightStart.val) {
            tail.next = leftStart;
            tail = tail.next;
            leftStart = leftStart.next;
            tail.next = null;
        } else {
            tail.next = rightStart;
            tail = tail.next;
            rightStart = rightStart.next;
            tail.next = null;
        }
    }
    if (leftStart == null) {
        tail.next = rightStart;
        listTail = tail;
        while (listTail.next != null) listTail = listTail.next;
    } else {
        tail.next = leftStart;
        listTail = tail;
        while (listTail.next != null) listTail = listTail.next;
    }
    return new ListNode[]{root.next, listTail};
}
历史评论
开始评论