描述

给定一个节点数为n的无序单链表，对其按升序排序。

思路1：辅助数组

1. 遍历保存到数组中
2. 对数组排序
3. 重新构造链表

思路2：小顶堆

1. 遍历构造小顶堆，遍历过程中
2. 再一个一个取出，连接

public class Solution {
    public ListNode sortInList (ListNode head) {
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((node1, node2)-> node1.val - node2.val);
        ListNode pre = null;
        while(head != null) {
            queue.offer(head);
            pre = head;
            head = head.next;
            pre.next = null;
        }
        ListNode dummyNode = new ListNode(-1);
        ListNode p = dummyNode;
        while(!queue.isEmpty()) {
            p.next = queue.poll();
            p = p.next;
        }
        p.next = null;
        return dummyNode.next;
    }
}

思路3：归并排序

1. 使用快慢指针找到中点，快指针一次前进两步，慢指针一次前进一步
2. 将链表断开，分成两部分
3. 分别对两段链表进行排序
4. 合并两段链表，比较头节点

public class Solution {
    public ListNode sortInList (ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        //快慢指针找到中点
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        //断开链表，分成两段
        slow.next = null;
        //分别对两段链表进行排序
        ListNode left = sortInList(head);
        ListNode right = sortInList(tmp);
        //合并两段链表，比较头节点
        ListNode newNode = new ListNode(-1);
        ListNode p = newNode;
        while(left != null && right != null) {
            if(left.val <= right.val) {
                p.next = left;
                left = left.next;
            } else if(left.val > right.val) {
                p.next = right;
                right = right.next;
            }
            p = p.next;
        }
        if(left != null) {
            p.next = left;
        }
        if(right != null) {
            p.next = right;
        }
        return newNode.next;
    }
}