**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