147.insertion-sort-list.cpp

/*
 * @lc app=leetcode id=147 lang=cpp
 *
 * [147] Insertion Sort List
 *
 * https://leetcode.com/problems/insertion-sort-list/description/
 *
 * algorithms
 * Medium (35.61%)
 * Total Accepted:    135.3K
 * Total Submissions: 379.8K
 * Testcase Example:  '[4,2,1,3]'
 *
 * Sort a linked list using insertion sort.
 * 
 * 
 * 
 * 
 * 
 * A graphical example of insertion sort. The partial sorted list (black)
 * initially contains only the first element in the list.
 * With each iteration one element (red) is removed from the input data and
 * inserted in-place into the sorted list
 * 
 * 
 * 
 * 
 * 
 * Algorithm of Insertion Sort:
 * 
 * 
 * Insertion sort iterates, consuming one input element each repetition, and
 * growing a sorted output list.
 * At each iteration, insertion sort removes one element from the input data,
 * finds the location it belongs within the sorted list, and inserts it
 * there.
 * It repeats until no input elements remain.
 * 
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: 4->2->1->3
 * Output: 1->2->3->4
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: -1->5->3->4->0
 * Output: -1->0->3->4->5
 * 
 * 
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	ListNode* insert(ListNode* head, ListNode* node){
		if(node->val <= head->val){
			node->next = head;
			return node;
		}
		ListNode* ret = head;
		while(head->next!=NULL && head->next->val < node->val)
			head = head->next;
		ListNode* tmp = head->next;
		head->next = node;
		node->next = tmp;
		return ret;
	}
    ListNode* insertionSortList(ListNode* head) {
    	if(head == NULL)	return NULL;
        ListNode* sorted = head; head = head->next;
        sorted->next = NULL;

        while(head!=NULL){
        	ListNode* next = head->next;
        	sorted = insert(sorted, head);
        	head = next;
        }
        return sorted;
    }
};