#include <stdio.h>

#include <stdlib.h>

#include <time.h>

struct ListNode {

};

ListNode *insertionSortList(ListNode *head) {

// zero or one element in list

if (head == NULL || head->next ==NULL){

return head;

}

ListNode *pSorted = NULL;

while ( head != NULL ){

/* remember the head */

ListNode *pHead = head;

/* trailing pointer for efficient splice */

ListNode **ppTrail = &pSorted;

/* pop head off list */

head = head->next;

/* splice head into sorted list at proper place */

while( *ppTrail!=NULL && pHead->val > (*ppTrail)->val ) {

ppTrail = &(*ppTrail)->next;

}

pHead->next = *ppTrail;

*ppTrail = pHead;

}

return pSorted;

}

void printList(ListNode* h)

}

ListNode* createList(int a[], int n)

{

ListNode *head=NULL, *p=NULL;

for(int i=0; i<n; i++){

if (head == NULL){

head = p = new ListNode(a[i]);

}else{

p->next = new ListNode(a[i]);

p = p->next;

}

}

return head;

}

int main(int argc, char** argv)

}