173. Insertion Sort List

Leave a comment

May 18, 2016 by oneOokay

public ListNode insertionSortList(ListNode head) {

ListNode dummy = new ListNode(0);  // here we dont need dummy.next = head, it is handled in the while loop.
while(head != null){ // “head” node is the targeted node that we are currently trying to find a right spot for.
ListNode node = dummy; // every time start from the dummy head & do the comparison for each already linked node.
//start the loop
while(node.next != null && node.next.val < head.val){
node = node.next;
} //node.next.val >= head.val

//swap head with node.next

//actually after first loop, it is forming a linked list starts with the dummy node and ends with null. this is a very smart solution. 
ListNode temp = head.next;
head.next = node.next;
node.next = head;
head = temp;
}
return dummy.next;
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: