LeetCode - 147. 对链表进行插入排序

题目解析

要求我们给链表排序，并规定是 插入排序算法.
可参考这篇文章Common Sort - 常见的几种排序 与 不常见的几种排序

解题思路

思路： 建立一个傀儡头节点newHead，使其链表成为一个带头的（newH.next = head）。
定义 一个引用指针 lastSorted = head；和 cur = head.val；
cur就是要进行插入排序的数据，而lastSorted 用来寻找比 cur.val值大的节点。

需要进行插入排序的数据，可能不止一个，所以循环一个循环。

然后，就是lastSorted 用来寻找比 cur.val值大的节点。

既然，现在后继节点找到了，那么，接下来我们就只需要找到 前驱节点【val值 比 cur 小】。所以，我们只需要在定义一个节点引用 prev，从傀儡出发，寻找 cur 的 前驱节点。
利用 前驱节点prev 和 后驱节点lastSorted，进行插入操作。

此时这到题不就完成了！最后返回 newHead.next 就OK了。

代码如下：

/**
 * 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) {
        if(head == null){
            return head;
        }
        ListNode newHead = new ListNode();
        newHead.next =  head;
        ListNode lastSorted = head;
        ListNode cur = head.next;
        while(cur != null){
            if(lastSorted.val <= cur.val){
                lastSorted = lastSorted.next;
            }else{
                ListNode prev = newHead;
                while(prev.next.val <= cur.val){
                    prev = prev.next;
                }
                lastSorted.next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
            }
            cur = lastSorted.next;
        }
        return newHead.next;
    }
}

代码细节

有兴趣的可以点进去看看

LeetCode所有的链表题的题解都这里哦，除了vip 和 关于 Hash 的题外，几乎都在里面。 二叉树、排序、堆，栈，队列 的题，正在一步步完善。