排序链表「变题」

148. 排序链表

变题一：归并 (递归)

// 时间复杂度 : O(nlogn)
// 空间复杂度 : 栈空间 O(logn)
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode prev = null, slow = head, fast = head;
    while (fast != null && fast.next != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = null;
    return merge(sortList(head), sortList(slow));
}
// 合并两个链表
private ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }
    if (l1 != null) p.next = l1;
    else if (l2 != null) p.next = l2;
    return dummy.next;
}

变题二：归并 (非递归)

xxxxxxxxxx
// 时间复杂度 : O(nlogn)
// 空间复杂度 : O(1)
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    int n = 0;
    ListNode p = head;
    while (p != null) {
        p = p.next;
        n++;
    }
    ListNode dummy = new ListNode(0, head);
    // 从长度为 1 的链表开始
    for (int i = 1; i < n; i += i) {
        p = dummy;  // 从头开始
        while (p.next != null) {
            ListNode h1 = p.next, cur = p;       // h1 是第一部分链表的头节点
            // 第一部分链表范围 [p.next, cur]
            for (int j = 0; j < i && cur.next != null; j++) {
                cur = cur.next;
            }
            ListNode h2 = cur.next, last = cur;  // h2 是第二部分链表的头节点
            // 第二部分链表范围 [last.next, cur]
            for (int j = 0; j < i && cur.next != null; j++) {
                cur = cur.next;
            }
            // 记录下次两部分链表的头节点
            ListNode t = cur.next;
            last.next = null;  // 断开连接
            cur.next = null;   // 断开连接
            p.next = merge(h1, h2);  // 合并两部分链表
            while (p.next != null) p = p.next;  // 遍历得到合并后链表的尾部
            p.next = t;  // 接上下次两部分链表的头节点
        }
    }
    return dummy.next;
}
private ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }
    if (l1 != null) p.next = l1;
    else if (l2 != null) p.next = l2;
    return dummy.next;
}

变题三：快排

// 时间复杂度 : O(nlogn)
// 空间复杂度 : 栈空间 O(logn)
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode dummySmall = new ListNode(0), dummyLarge = new ListNode(0);
    ListNode small = dummySmall, large = dummyLarge;
    ListNode slow = head, fast = head, prev = null;
    while (fast != null && fast.next != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = slow.next;
    slow.next = head;

    ListNode pivot = slow;
    ListNode p = pivot.next;
    while (p != null) {
        if (p.val < pivot.val) {
            small.next = p;
            small = small.next;
        } else {
            large.next = p;
            large = large.next;
        }
        p = p.next;
    }
    small.next = null;
    large.next = null;

    dummySmall.next = sortList(dummySmall.next);
    pivot.next = sortList(dummyLarge.next);

    p = dummySmall;
    while (p.next != null) {
        p = p.next;
    }
    p.next = pivot;

    return dummySmall.next;
}