LeetCode 147:Insertion Sort List

Sort a linked list using insertion sort.

//鏈表插入排序
//對於當前遍歷的cur點，判斷前面是否可以插入，若可以插入，則當前遍歷點cur指向插入點的後一點，插入點的前一點指向cur
//然後再將前面已經排好序的鏈表的最後一個節點，指向cur的下一個節點。
//利用臨時變量tmp記錄當前遍歷節點的下一個節點，以便繼續遍歷下個節點

class Solution {
public:
	ListNode* insertionSortList(ListNode* head) {
		ListNode dummy(INT_MIN);
		ListNode*  cur = head;
		while (cur !=nullptr)
		{
			ListNode* pos = findInsertPos(&dummy, cur->val);
			ListNode* tmp = cur->next; //記錄當前遍歷節點的下一個節點，以便繼續遍歷下個節點
			cur->next = pos->next;
			pos->next = cur;
			cur = tmp;
		}
		return dummy.next;
	}
	//找到當前遍歷點cur的插入位置
	ListNode* findInsertPos(ListNode *head, int x){
		ListNode* pre=nullptr ;
		ListNode* cur= head;
		while (cur !=nullptr && cur->val<=x)
		{
			pre = cur;
			cur = cur->next;
		}
		return pre;
	}
};