My simple Java Solution (win 88%)


  • 0
    C

    To make a insertion sort, the first thing we do is to new a sorted list, and ensure the asending order between pre and sorted (two pointer) and insert the value in head into the sorted list.

    public class Solution {
        public ListNode insertionSortList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode pre = new ListNode(-11);
            ListNode sorted = new ListNode(head.val);
            pre.next = sorted;
            head = head.next;
            while(head != null) {
                if(head.val < sorted.val) {
                    ListNode tempPre = pre;
                    while(pre.next != null && pre.next.val < head.val) {
                        pre = pre.next;
                    }
                    ListNode temp = pre.next;
                    pre.next = new ListNode(head.val);
                    pre.next.next = temp;
                    pre = tempPre;
                } else {
                    sorted.next = new ListNode(head.val);
                    sorted = sorted.next;
                }
                head = head.next;
            }
            return pre.next;
        }
    
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.