[LeetCode 147]Insertion Sort List

/**
 * 
	Sort a linked list using insertion sort.
 *
 */
public class InsertionSortList {

	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}
	
//	21 / 21 test cases passed.
//	Status: Accepted
//	Runtime: 312 ms
//	Submitted: 0 minutes ago

	//時間復雜度O(n * n) 空間復雜度 O(1)
	public ListNode insertionSortList(ListNode head) {
		ListNode preHead = new ListNode(-1);
		while(head != null) {
			ListNode cur = preHead;
			int val = head.val;
			while(cur.next != null) {
				if(cur.next.val >= val) {
					break;
				}
				cur = cur.next;
			}
			ListNode curNext = cur.next;
			cur.next = head;
			head = head.next;
			cur.next.next = curNext;
		}
		return preHead.next;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}