Accepted and clean golang solution without extra space (O(1))


  • 0
    V

    Idea:
    If el < previous we need to find the right place for it, in default insertion sort for the array you will go left, in our case we can't do this and will go from the head, because list[head:previos] is sorted. So just find the right place and put it by manipulating links.

    func InsertionSortList(head *ListNode) *ListNode {
    	if head == nil {
    		return nil
    	}
    	current := head.Next
    	previous := head
    	dumpHead := head
    	var prevSearch *ListNode
    
    	for current != nil {
    		if previous.Val > current.Val {
    			search := dumpHead
    			prevSearch = nil
                            //find the right place to put element before
    			for search != nil && (current.Val > search.Val || search == current) {
    				prevSearch = search
    				search = search.Next
    			}
    			previous.Next = current.Next
    			current.Next = search
    
    			//put before head
    			if prevSearch == nil {
    				dumpHead = current
    			} else {
    				prevSearch.Next = current
    			}
    
    			current = previous.Next
    		} else {
    			previous = current
    			current = current.Next
    		}
    	}
    
    	return dumpHead
    }
    

Log in to reply
 

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