Sort List (Insert Sort)

来源：Leetcode

原帖：http://oj.leetcode.com/problems/insertion-sort-list/

题目：
Sort a linked list using insertion sort.

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
     ListNode *insertionSortList(ListNode *head) {  
         if(!head) return NULL;  
         ListNode dummy(0); // 1->2->5->null insert 3;     
         while (head) { // head: insert linked list node  
             ListNode* node = &dummy;  
             while (node->next != NULL && node->next->val <= head->val) {  
                 node = node->next;  
             }       
             ListNode* temp = head->next;  
             head->next = node->next;  
             node->next = head;  
             head = temp;  
         }  
         return dummy.next;  
     }  
 };