Question

Algorithm of Insertion Sort:

  1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
  2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
  3. It repeats until no input elements remain.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Thinking:

  • Method : TLE
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        if(head == null || head.next == null)  return head;
        dummy.next = head;
        ListNode pre1 = head;
        ListNode cur1 = head.next;
        ListNode pre2 = null;
        ListNode cur2 = null;
        while(cur1 != null){
            pre2 = dummy;
            cur2 = dummy.next;
            while(cur1 != null && cur2 != null && cur2 != cur1){
                if(cur1.val < cur2.val){
                    swap(pre1, cur1, pre2, cur2);
                    break;
                }else{
                    cur2 = cur2.next;
                    pre2 = pre2.next;
                }
            }
            pre1 = cur1;
            cur1 = cur1.next;
        }
        return dummy.next;
    }
    private void swap(ListNode pre1, ListNode cur1, ListNode pre2, ListNode cur2){
        pre1.next = cur2;
        ListNode next = cur2.next;
        cur2.next = cur1.next;
        pre2.next = cur1;
        cur1.next = next;
    }
}
  • Method 2:AC
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        ListNode cur = head;
        ListNode ans = dummy;
        while(cur != null){
            ans = dummy;
            while(ans.next != null && ans.next.val < cur.val){
                ans = ans.next;
            }
            ListNode next = cur.next;
            cur.next = ans.next;
            ans.next = cur;
            cur = next;
        }
        return dummy.next;
    }
}

二刷

  1. TLE 
    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
 public ListNode insertionSortList(ListNode head) {
     if(head == null) return head;
     ListNode dummy = new ListNode(0);
     dummy.next = head;
     ListNode cur = dummy.next;
     ListNode precur = dummy;
     while(cur != null){
         ListNode cur1 = dummy.next;
         ListNode precur1 = dummy;
         while(cur1.val <= cur.val && cur1 != cur){
             cur1 = cur1.next;
             precur1 = precur1.next;
         }
         if(cur.val < cur1.val){
             precur.next = cur.next;
             precur1.next = cur;
             cur.next = cur1;
         }else{
             precur = cur;
             cur = cur.next;
         }
     }
     return dummy.next;
 }
}
  2. 参考了一刷的AC结果,这个结果通过dummy这个节点忽略了对两个pre的记录。并且通过不断将结点挂载在dummy引出的新链上，让结果更为简洁。 
    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
 public ListNode insertionSortList(ListNode head) {
     if(head == null || head.next == null) return head;
     ListNode dummy = new ListNode(0);
     ListNode cur = head;
     ListNode temp = null;
     while(cur != null){
         temp = dummy;
         while(temp.next != null && temp.next.val < cur.val){
             temp = temp.next;
         }
         ListNode next = cur.next;
         cur.next = temp.next;
         temp.next = cur;
         cur = next;
     }
     return dummy.next;
 }
}