Java Solution: A little trick beats 90%


  • 2
    public class Solution {
        public ListNode insertionSortList(ListNode head) {
            if(head==null||head.next==null)
                return head;
            ListNode fakeHead=new ListNode(1);
            ListNode pre = fakeHead;
            
            while(head!=null){
                // important trick here to avoid scanning from head.
                if(pre!=fakeHead && pre.val>head.val) 
                    pre=fakeHead;
                while(pre.next!=null && pre.next.val<head.val){
                    pre=pre.next;
                }
                ListNode cur=head;
                head=head.next;
                cur.next=pre.next;
                pre.next=cur;
            }
            return fakeHead.next;
        }
    }

Log in to reply
 

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