Insertion Sort List

Insertion Sort List

 

Sort a linked list using insertion sort.

 

Naive Way:Insertion Sort是和Bubble Sort类似的一种，不断将元素插入到已排好序的序列中的排序算法 。那么一开始排好序的就只有head一个节点，然后将后面的节点不断的插入到排好序的节点中。

 

算法复杂度必须是O(n^2)，space O(1)。得注意待插入的节点的next指针要先清理掉，否则后面一整串跟着带进来了。

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode newHead = new ListNode(0);
        ListNode cur = head;
        ListNode pre = cur;
        while(cur!=null){
            pre = cur;
            cur = cur.next;
            pre.next = null;
            insert(newHead, pre);
        }
        return newHead.next;
    }
    
    private void insert(ListNode head, ListNode node){
        if(node==null){return;}
        ListNode pre = head;
        ListNode cur = pre;
        boolean found = false;
        while(cur.next!=null){
            pre = cur;
            cur = cur.next;
            if(cur.val > node.val){
                node.next = cur;
                pre.next = node;
                found = true;
                break;
            }
        }
        if(!found)
            cur.next = node;
    }
}