🌗 147. 对链表进行插入排序

难度: 🌗

问题描述

---

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        // 思路：
        // 将链表分成两部分，初始时，left 只有一个首元素，剩余元素在 right 链表
        // left 为排好序的链表, right 为待插入链表节点
        if(head == null || head.next == null) {
            return head;
        }
        // 节点数 >= 2
        ListNode left = new ListNode(-1); // 虚拟节点，便于直接插入最前面
        left.next = head;
        ListNode tail = head; // 记录排序链表的末尾节点，便于直接插入尾部
        ListNode right = head.next;
        head.next = null; // 切断 left & right 的连接
        while(right != null) {
            ListNode next = right.next;
            right.next = null; // 切断新插入节点与后续节点的连接
            if(right.val <= left.next.val) {
                ListNode tmp = left.next;
                left.next = right;
                right.next = tmp;
            } else if(right.val >= tail.val) {
                tail.next = right;
                tail = tail.next;
            } else {
                // right 应该插入已排序链表的中间，顺序查找
                ListNode cur = left.next;
                ListNode pre = left;
                while(right.val > cur.val) {
                    pre = cur;
                    cur = cur.next;
                }
                // right.val <= cur.val 在 pre 后面插入 right
                pre.next = right;
                right.next = cur;
            }
            right = next;
        }
        return left.next;
    }
}

---

输出