LeetCode-148-排序链表

148. 排序链表

难度中等

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

进阶：

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

示例 1：

img

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

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 题。

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;
    }

}

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;
    }
}

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
}

image-20210618091147563