LeetCode——对链表进行插入排序&排序链表

对链表进行插入排序 中等 、排序链表 中等

NO.147 对链表进行插入排序 中等

思路一：插入排序 思路题目上已经给了，就是动手实现就行了。

1. 寻找需要插入排序的节点 next；
2. 从 [表头,next] 区间内寻找到最后一个小于等于 next 的节点 pre；
3. 将 next 节点插入到 pre 节点的后面。

public ListNode insertionSortList(ListNode head) {
    ListNode dummy = new ListNode(Integer.MIN_VALUE);
    dummy.next = head;
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        //当发生逆序的时候才需要进行插入排序
        if (next != null && next.val < cur.val) {
            //pre 寻找 next 节点插入的位置的前驱
            while (pre.next != null && pre.next.val <= next.val) {
                pre = pre.next;
            }
            //插入操作,next 插入到 pre节点的后面
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
            //pre 指针重置
            pre = dummy;
        } else {
            //当前是有序的,不需要插入排序
            cur = next;
        }
    }
    return dummy.next;
}

时间复杂度：O(n^2) 插入排序

NO.148 排序链表 中等

思路一：归并排序 O(nlogn)的时间复杂度，要求对链表进行归并排序，而且空间是O(1)。

归并排序的过程，先快慢指针找到中点，对半拆分链表，直至子链表剩余一个节点，再重新合并有序链表。

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 head2 = slow.next;
    slow.next = null;
    ListNode left = sortList(head);
    ListNode right = sortList(head2);
    //合并有序链表
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    while (left != null && right != null) {
        if (left.val <= right.val) {
            p.next = left;
            left = left.next;
        } else {
            p.next = right;
            right = right.next;
        }
        p = p.next;
    }
    p.next = left != null ? left : right;
    return dummy.next;
}

时间复杂度：O(nlogn) 空间复杂度：O(logn) 递归栈使用的空间。

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github