[LeetCode] 147. Insertion Sort List

轉自LeetCode

Sort a linked list using insertion sort.

<Solution>
這題是要對 linked list 實現 insertion sort

按照 insertion sort 的演算法，搭配 linked list 這個資料結構操作即可

code 如下

	/**
	* 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) {
	ListNode *dummyH = new ListNode(-1);
	ListNode *curNode, *nextNode;
	while(head) {
	nextNode = head->next;
	curNode = dummyH;
	//>> find correct position to insert
	while(curNode->next && curNode->next->val <= head->val) {
	curNode = curNode->next;
	}
	head->next = curNode->next;
	curNode->next = head;
	head = nextNode;
	}
	return dummyH->next;
	}
	};

view raw insertionSortOfLinkedList_1.cpp hosted with ❤ by GitHub