Insertion Sort List

Sort a linked list using insertion sort.

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode header = new ListNode (0); 

        //Pointer of LinkedList started with head   (List1)
        ListNode cur1 = head; 
        //Pointer of LinkedList started with header (List2)
        ListNode cur2 = null; 
        //The next ListNode of cur1 
        ListNode curNext = null;
        /*
         * Take ListNode out of List1, and put it in List2 
         */
        while (cur1!=null) {
            curNext = cur1.next;
            cur2 = header; 
            while (cur2.next != null) {
                //Compare cur1.val with the the value of the cur2.next
                if (cur1.val >= cur2.next.val) {
                    cur2 = cur2.next; 
                    continue; 
                } else 
                    break;
            }
            cur1.next = cur2.next;
            cur2.next = cur1;
            cur1 = curNext; 
        }
        return header.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