LeetCode 148. Sort List(排序链表 java)

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

示例

示例 1:
输入: 4->2->1->3
输出: 1->2->3->4

示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路

• 相比普通的数组排序,链表无法逆向遍历
• 可以模拟各类数组排序进行编写,一般高效且较难理解
• 可以转为数组,用数组排序,排序后重建链表

代码1

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode cur = head;
        int count = 0;
        //获取长度
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        int[] arr = new int[count];
        int index = 0;
        cur = head;
        //值导入数组
        while (cur != null) {
            arr[index++] = cur.val;
            cur = cur.next;
        }
        //排序
        Arrays.sort(arr);
        
        cur = head;
        index = 0;
        //重新赋值
        while (cur != null) {
            cur.val = arr[index++];
            cur = cur.next;
        }
        return head;
    }

分析

• 简单的思路,转为数组->排序->重建链表,方法取巧
• 当节点对象复杂化时,需要创建多个数组保存数据映射,效率会快速下降
• 使用方法Arrays.sort(arr);进行数组排序,该方法使用优化的快速排序,对比其他排序效率很高

代码2

该问题效率排行最高的算法,用连表操作模拟归并排序,但是代码较难理解

// 模拟归并排序
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        return merge(l1, l2);
    }

    //比较用工具方法
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode l = new ListNode(0);
        ListNode p = l;
        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;
        if (l2 != null)
            p.next = l2;
        return l.next;
    }

总结

1. 链表排序能够模拟数组排序的方法,但由于无法逆向遍历,方法需要很多改变和优化
2. 链表对象结构简单时,可以使用转为数组的方式进行操作
3. 需要多熟悉链表操作的方法和技巧
4. 轻喷