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

147.对链表进行插入排序

题目

对链表进行插入排序。

示例 1：
输入: 4->2->1->3
输出: 1->2->3->4

示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5

方法一

新建一个列表，将链表中的元素全部加入到这个链表中。然后对这个列表进行排序。最后将列表中排序好的元素再依次放回链表中。

public ListNode insertionSortList(ListNode head) {
    List<Integer> list = new ArrayList<>();
    ListNode cur = head;
    while(cur != null){
        list.add(cur.val);
        cur = cur.next;
    }
    Collections.sort(list);
    cur = head;
    for(int num : list){
        cur.val = num;
        cur = cur.next;
    }
    return head;
}

方法二

设置一个指针pre和一个指针cur，pre初始化为head，cur初始化为head.next。从前到后遍历链表中的每一个元素

• 如果pre所指的值小于cur所指的值（已经有序），那么pre和cur正常向后移动
• 如果pre所指的值大于cur所指的值，那么cur所指节点需要在前面已经有序的部分找到相应位置进行插入。

public ListNode insertionSortList(ListNode head) {
    //链表为空或者只有一个节点的情况
    if(head == null || head.next == null)
        return head;
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = head, cur = head.next;
    while(cur != null){
        if(pre.val <= cur.val){
            pre = cur;
            cur = cur.next;
        }
        else{
            //节点node用来遍历找到插入位置
            ListNode node = dummy;
            //找到一个位置，使得node < cur < node.next
            while(node.next != null && node.next.val < cur.val)
                node = node.next;
            //将原有位置的cur删除
            pre.next = cur.next;
            //将cur插入到新位置
            cur.next = node.next;
            node.next = cur;
            //插入结束后，cur回到原有位置（pre后面），继续后面的遍历
            cur = pre.next;
        }
        return dummy.next;
    }