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

题目

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

• 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
• 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
  重复直到所有输入数据插入完为止。

示例 1：

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

示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解答

解法一：非递归

理解了插入排序，代码也很好写。

要点如下：

1. 声明一个有虚拟头结点的空链表作为结果链表。
2. 每遍历一个结点，在结果链表中找到该结点的插入位置。
3. 将结点插入到对应的位置。

复杂度分析：O(n^2) 的时间，O(1) 的空间

效率上是正常的，但是为什么百分比这么低呢？

• 看解答发现有的人在这题用了 O(nlogn) 的高级排序。。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode root = new ListNode(0);
        ListNode p = head;
        while(p != null) {
            ListNode pre = root;
            while(pre.next != null && pre.next.val <= p.val) {
                pre = pre.next;
            }
            
            ListNode next = p.next;
            p.next = pre.next;
            pre.next = p;
            p = next;
        }
        
        return root.next;
    }
}

结果

解法二：递归

insert 方法的宏观语义：找到 node 结点的插入位置，并返回新链表的头部 。（明白这个方法的意义，这题就解决了）

所以本题就简化成：向一个空链中将原链表的结点一个一个插入进去。

复杂度分析：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 || head.next == null) return head;
        
        ListNode res = null;
        ListNode p = head;
        while(p != null) {
            ListNode next = p.next;
            res = insert(res, p);
            p = next;
        }
        
        return res;
    }
    
    private ListNode insert(ListNode head, ListNode node) {
        if(head == null || head.val > node.val) {
            node.next = head;
            return node;
        }
        
        head.next = insert(head.next, node);
        return head;
    }
}

结果