题目地址 (opens new window)

• 🙂 第一次练习 2020-11-21 运用插入排序的思想 整体思路是明确的，此题需要注意链表的转换操作。
• 😄 第二次练习

解题方法

时间复杂度: O(n^2)
空间复杂度: O(1)

如上图所示，题目中要求通过插入排序的方式对连表进行排序。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
       if (head == null) {
           return null;
       }

       ListNode dummyHead = new ListNode(-1);
       dummyHead.next = head;
       ListNode last = head;
       ListNode curr = head.next;

       while(curr != null){
            // 如果当前节点 小于 排序部分 尾结点
            if (curr.val >= last.val) {
                last = last.next;
            } else {
                ListNode prev = dummyHead;
                while(prev.next.val <= curr.val) {
                    prev = prev.next;
                }

                // 移动有序链表端 到尾部
                last.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }

            curr = last.next;
       }
       return dummyHead.next;
    }
}

易错点

• 虚拟 头结点的运用