LeetCode Q147: Insertioin 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==NULL)
	return head;
	ListNode* myHead=new ListNode(-1);
	while(head!=NULL){
	ListNode* target=head;
	head=head->next;
	target->next=NULL;
	ListNode* p=myHead;
	while(true){
	if(p->next==NULL){
	p->next=target;
	break;
	}
	if(target->val<=p->next->val){
	target->next=p->next;
	p->next=target;
	break;
	}
	if(target->val>p->next->val){
	p=p->next;
	continue;
	}
	}
	}
	return myHead->next;
	}
	};

view raw Q147InsertionSortLinkedList.cpp hosted with ❤ by GitHub

Round 2 solution: I just aware that my 1st round solution is actually bubble sort. The insertion sort is given in below:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	void sort(ListNode*& head, ListNode* node){
	node->next=NULL;
	ListNode* p=head;
	if(node->val<=head->val){
	node->next=p;
	head=node;
	return;
	}
	while(p->next!=NULL){
	if(node->val>p->val&&node->val<=p->next->val){
	ListNode* tmp = p->next;
	p->next=node;
	node->next=tmp;
	break;
	}
	p=p->next;
	}
	if(p->next==NULL)
	p->next=node;
	}
	ListNode* insertionSortList(ListNode* head) {
	if(head==NULL)
	return head;
	ListNode* p = head;
	ListNode* newHead=NULL;
	while(p!=NULL){
	if(newHead==NULL){
	newHead=p;
	p=p->next;
	newHead->next=NULL;
	}else{
	ListNode* tmp = p->next;
	sort(newHead, p);
	p=tmp;
	}
	}
	return newHead;
	}
	};

view raw Q147Rnd2.cpp hosted with ❤ by GitHub