147. Insertion Sort List

Sort a linked list using insertion sort.

思路：插入排序

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }

         ListNode dummy = new ListNode(0);
         ListNode prev = dummy;
         ListNode curr = head;
         ListNode next = curr;

         while(curr!=null){
             next = curr.next;
             while (prev.next!=null&&prev.next.val<curr.val){
                 prev = prev.next;
             }
             curr.next = prev.next;
             prev.next = curr;
             prev = dummy;
             curr = next;
         }
        return dummy.next;    
    }
}

LG CODE

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution{
    public ListNode insertionSortList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;


        while(head != null && head.next !=null){
            if(head.val < head.next.val){
                head = head.next;
            }else{
                ListNode curr = dummy;
                while(curr.next.val < head.next.val){
                    curr = curr.next;
                }
                ListNode tmp = head.next;
                head.next = tmp.next;
                tmp.next = curr.next;
                curr.next = tmp;
            }
        }
                return dummy.next;    
    }
}