My accepted Java code


  • 0
    L
    public class Solution {
        public ListNode insertionSortList(ListNode head) {
            if (head==null || head.next==null) return head;
            ListNode curr=head.next, tail=head,helper=null;
            while (curr!=null){
                helper=head;
                if (helper.val>=curr.val){
                    tail.next=curr.next;
                    curr.next=helper;
                    head=curr;
                    curr=tail.next;
                }else if (curr.val>=tail.val){
                    tail=tail.next;
                    curr=curr.next;
                }else{
                    while(helper.next.val<curr.val){
                        helper=helper.next;
                    }
                    tail.next=curr.next;
                    curr.next=helper.next;
                    helper.next=curr;
                    curr=tail.next;
                }
            }
            return head;
        }
    }

  • 0
    N

    My thought is making two links.One is sorted, the other is the unchanged.
    every time i pick the head of the old one, and iput it into the sorted link.

    	if(head == null) return null;
    	if(head.next == null) return head;
    	
    	ListNode temp, hold, hold2, tempNext, pret;
    	pret = head;
    	temp = head.next;
    	pret.next = null;
    	for (;temp != null; temp = tempNext){
    		tempNext = temp.next;
    		if(temp.val <= head.val) {
    			hold = head;
    		//	pret.next = temp.next;
    			temp.next = hold;
    			head = temp;
    //			System.out.print( "bbb ");
    			
    		} else {
    //			System.out.print( "ccc ");
    			for(hold = head, hold2 = head; hold.next !=null&&hold.val < temp.val; hold = hold.next){
    			
    				hold2 = hold;
    //				System.out.print( "cddd ");
    			}	
    			if(hold.val < temp.val){
    				hold.next = temp;
    				temp.next = null;
    				} else {
    				hold2.next = temp;
    				temp.next = hold;
    				}
    
    		}
    		
    //		i = head;
    //		while (i !=null ) {
    //			System.out.print(i.val + " ");
    //			i = i.next;
    //		}
    //		System.out.print( "aaa ");
    	}
    	
    	
    	return head;
    

Log in to reply
 

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