Insertion Sort List

Sort a linked list using insertion sort.

The algorithm is relatively simple, but pay attention to details when doing the insert. And if one number can not be inserted, it should be appended to the sorted list. This should be treated seperately

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode helper = new ListNode(Integer.MIN_VALUE);
        helper.next = head;
        ListNode end = helper.next;
        while(end.next!= null) { //the end of the sorted list
            ListNode insert = helper.next;
            ListNode insert2 = helper; // to help insert to correct position
            boolean found = false;
            while(insert != end.next) {
                //this insertion is a little bit confusing
                if (insert.val > end.next.val) {
                    insert2.next = end.next; //insert2 points to end.next
                    end.next = end.next.next; // end.next points to next, no need to advance end if insert in the middle
                    insert2.next.next = insert; // connect the newly inserted list
                    found = true;
                    break;
                }
                else {
                    insert = insert.next;
                    insert2 = insert2.next;
                }
            }
            if (!found) // the end.next should just append to sorted list
                end = end.next;
            
        }
        return helper.next;
    }
}

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