Tags

,

=======Java===========
/*
Sort a linked list using insertion sort.
"https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Insertion_sort.html"
make sure you understand what is insertion sort first! The whole idea is, have one sorted list, and another unsorted remaining list. now, for each item in the remaining list, insert it into the sorted list.
Pay attention to how fake head is used here: sortedHd, which is pretty common in linked list related algorithm.

T(N) = O(N^2)
space: O(1)

*/

/**
 * 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)
            return null;
        //make a fake head to represent the sorted-list
        ListNode sortedHd = new ListNode(0);
        //current code which will be inserted into the sorted-list
        ListNode cur = head;
        while(cur != null)
        {
            ListNode sortedNd = sortedHd;
            //find the first value in sorted-list which is larger than cur.val
            while(sortedNd.next != null && sortedNd.next.val <= cur.val)
                sortedNd = sortedNd.next;
            //now, cur should be inserted after sortedNd
            ListNode curNext = cur.next;
            cur.next = sortedNd.next;
            sortedNd.next = cur;
            cur = curNext;
        }
        return sortedHd.next;
    }
}
Advertisements