147. Insertion Sort List.md

147. Insertion Sort List

Problem

Sort a linked list using insertion sort.

tag:

• sort

Solution

链表的插入排序：

1. 记录当前元素的下一个节点位置
2. 遍历已排好序的结果链表，找到插入位置
3. 向结果链表中插入当前元素
4. 恢复当前到下一个节点位置

java

    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        while( head!=null ) {
            ListNode tmp = head.next; // save next node
            
            //find insert location;
            ListNode p = dummy;
            while(p.next!=null && head.val>p.next.val) {
                p = p.next;
            }
            //insert
            head.next = p.next;
            p.next = head;
            
            head = tmp; // recover head
        }
        return dummy.next;
    }

go