inertion sort

inertion sort

easy proble

This problem is used to pratice the basic skills and it is wroth to try many times.

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *insertionSortList(ListNode *head) {
12         if ( !head || !head->next ) {
13             return head;
14         }
15         ListNode* newHead = head;
16         ListNode* p = newHead;
17         ListNode* q = NULL;
18         head = head->next;
19         newHead->next = NULL;
20         while ( head ) {
21             q = head->next;
22             if ( head->val <= newHead->val ) {
23                 head->next = newHead;
24                 newHead = head;
25             } else {
26                 p = newHead;
27                 while ( p-> next && p ->next->val < head->val ) {
28                     p = p->next;
29                 }
30                 head->next = p->next;
31                 p->next = head;
32             }
33             head = q;
34         }
35         return newHead;
36     }
37 };

Loading Disqus comments...
Table of Contents