题目描述

解题思路

暴力

遍历后排序，在生成链表，空间复杂度不满足常数级

public ListNode sortList(ListNode head) {
    if (head == null) return null;
    ListNode cur = head;
    List<Integer> list = new ArrayList<>();
    while (cur != null) {
        list.add(cur.val);
        cur = cur.next;
    }
    Collections.sort(list);
    ListNode head1 = new ListNode(list.get(0));
    cur = head1;
    for (int i = 1; i < list.size(); i++) {
        cur.next = new ListNode(list.get(i));
        cur = cur.next;
    }
    return head1;
}

归并排序

递归版

详解参照🔗
归并排序的思路就是将链表一分为二，一直分割到1个链表才进行合并，分割采用前后指针的方法找出中间节点来进行分割，然后在进行合并，和21. 合并两个有序链表，双指针判断大小合并，最终连接上剩余的节点。

public ListNode sortList(ListNode head) {
    if (head == null && head.next == null) return head;
    // 前后指针找到中间节点
    ListNode slow = head, fast = head.next;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    // 递归将节点分开
    ListNode tmpNode = slow.next;
    // 注意设置为null,才是一个单链表
    slow.next = null;
    ListNode left = sortList(head);
    ListNode right = sortList(tmpNode);
    // 设置一个虚拟头节点，用来连接
    ListNode node = new ListNode(0);
    ListNode dummy = node;
    while (left != null && right != null) {
        if (left.val < right.val) {
            node.next = left;
            left = left.next;
        }else {
            node.next = right;
            right = right.next;
        }
        node = node.next;
    }
    // 合并还剩余的节点
    node.next = left == null ? right : left;
    // 返回头节点
    return dummy.next;
}

迭代版本

迭代版本直接操作链表，设置一个虚拟头节点用来记录头节点，使用一个变量intv来表示每次合并的区间，例如：

直到intv==链表长度，表示合并完成。

模拟上述操作：

// 迭代
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    // 使用虚拟头节点,来记录
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int len = getLength(head);
    int itrv = 1;
    // 合并的区间等于链表长度就不在合并
    while (itrv < len) {
        // 表示当前节点
        ListNode h = dummy.next;
        ListNode pre = dummy;
        while (h != null) {
            int i = itrv;
            ListNode h1 = h;
            for (; h != null && i > 0; i--) {
                h = h.next;
            }
            // 如果没有第二条链表，直接break
            if (i > 0) break;
            i = itrv;
            ListNode h2 = h;
            // 如果有，找到第二条链表
            for (; h != null && i > 0; i--) {
                h = h.next;
            }
            // 此时开始合并2个链表
            // 前部分链表的长度
            int left = itrv;
            // 后部分链表的长度，减i的情况就是如果后面链表长度不足itrv
            int right = itrv - i;
            while (left > 0 && right > 0) {
                if (h1.val < h2.val) {
                    pre.next = h1;
                    h1 = h1.next;
                    left--;
                } else {
                    pre.next = h2;
                    h2 = h2.next;
                    right--;
                }
                pre = pre.next;
            }
            // 连接剩余的
            pre.next = left > 0 ? h1 : h2;
            // 这对处理完，移动到最后，开始第二组，注意移动最长的
            // 第二段可以不等于itrv
            while (left > 0 || right > 0) {
                pre = pre.next;
                left--;
                right--;
            }
            // 第二段头节点赋值给第一段
            pre.next = h;
        }
        // 扩大两倍合并
        itrv *= 2;
    }
    return dummy.next;
}
public int getLength(ListNode head) {
    ListNode cur = head;
    int len = 0;
    while (cur != null) {
        cur = cur.next;
        len++;
    }
    return len;
}