程序员社区

LeetCode-148-排序链表

LeetCode-148-排序链表

148. 排序链表

难度中等

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表

进阶:

  • 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

示例 1:

LeetCode-148-排序链表插图
img
输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2:

LeetCode-148-排序链表插图1
img
输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目在范围 [0, 5 * 104]
  • -105 <= Node.val <= 105

题目大意

链表的排序,要求时间复杂度必须是 O(n log n),空间复杂度是 O(1)

解题思路

这道题只能用归并排序才能符合要求。归并排序需要的 2 个操作在其他题目已经出现过了,取中间点是第 876 题,合并 2 个有序链表是第 21 题。

LeetCode-148-排序链表插图2
image-20210618090921648

对数组做归并排序的空间复杂度为 O(n),分别由新开辟数组O(n)和递归函数调用O(logn)组成,而根据链表特性:

数组额外空间:链表可以通过修改引用来更改节点顺序,无需像数组一样开辟额外空间;
递归额外空间:递归调用函数将带来O(logn)的空间复杂度,因此若希望达到O(1))空间复杂度,则不能使用递归。

递归代码
class Solution {
   public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }

}
LeetCode-148-排序链表插图3
image-20210618092320547
迭代实现
// Iterative Merge Sort Solution
// Time complexity: O(NlogN)
// Space complexity: O(1)
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummyHead = new ListNode(0);//虚拟头结点
        dummyHead.next = head;
        ListNode cur = dummyHead;
        int len = getLength(head);
        for (int step = 1; step < len; step *= 2) {
            mergeSort(dummyHead, step);
        }
        return dummyHead.next;
    }
    
    private void mergeSort(ListNode dummyHead, int step) {
        ListNode prev = dummyHead, cur = dummyHead.next;
        while (cur != null) {
            ListNode head1 = cur;
            ListNode head2 = split(head1, step);  // split and return tail
            cur = split(head2, step);  // split and return tail
            prev = merge(head1, head2, prev);  // merge and return tail
        }
    }
    
    private ListNode split(ListNode head, int step) {
        if (head == null) return null;
        ListNode cur = head;
        while (cur.next != null && step > 1) { // leave 1 more step after while loop
            cur = cur.next;
            step--;
        }
        ListNode next = cur.next;
        cur.next = null;
        return next;
    }
    
    // Merge the two lists and return tail node.
    private ListNode merge(ListNode head1, ListNode head2, ListNode dummyHead) {
        ListNode p1 = head1, p2 = head2, cur = dummyHead;
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                cur.next = p1;
                p1 = p1.next;
            } else {
                cur.next = p2;
                p2 = p2.next;
            }
            cur = cur.next;
        }
        cur.next = p1 != null ? p1 : p2;
        // Get the tail
        while (cur.next != null) {
            cur = cur.next;
        }
        return cur;
    }
    
    private int getLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
}
LeetCode-148-排序链表插图4
image-20210618092823609
GO代码
func sortList(head *ListNode) *ListNode {
    length := 0
    cur := head
    for cur != nil {
        length++
        cur = cur.Next
    }
    if length <= 1 {
        return head
    }

    middleNode := middleNode(head)
    cur = middleNode.Next
    middleNode.Next = nil
    middleNode = cur

    left := sortList(head)
    right := sortList(middleNode)
    return mergeTwoLists(left, right)
}

func middleNode(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    p1 := head
    p2 := head
    for p2.Next != nil && p2.Next.Next != nil {
        p1 = p1.Next
        p2 = p2.Next.Next
    }
    return p1
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val < l2.Val {
        l1.Next = mergeTwoLists(l1.Next, l2)
        return l1
    }
    l2.Next = mergeTwoLists(l1, l2.Next)
    return l2
}
LeetCode-148-排序链表插图5
image-20210618091147563
赞(0) 打赏
未经允许不得转载:IDEA激活码 » LeetCode-148-排序链表

一个分享Java & Python知识的社区