程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 147:Insertion Sort List

LeetCode 147:Insertion Sort List

編輯:C++入門知識

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;
	}
};

\

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved