LeetCode—Insertion Sort List

Sort a linked list using insertion sort.

我的了解是通過插入排序法對連結清單進行排序的操作：

在連結清單中主要由兩個指針，一個是pre指向目前比較的節點的前一個節點，還有一個是pCur是代表目前節點

#include <iostream>
using namespace std;


struct ListNode {
	int val;
	ListNode *next;
};


class Solution {
public:
	ListNode *insertionSortList(ListNode *head) {
		if(!head || !head->next)
		{
			return head;
		}
		ListNode * pre = head;
		ListNode * pCur = head->next;
		while(pCur)
		{
			while (pre->next != pCur)
			{
				pre = pre->next;
			}
			if(pCur->val >= pre->val)
			{
				pCur = pCur->next;
				continue;
			}
			ListNode * pCurNext = pCur->next;
			pre->next = pCurNext;
			ListNode * p = head;
			while(p != pCur)
			{
				if(pCur->val <= p->val)
				{
					int temp = p->val;
					p->val = pCur->val;
					pCur->val = temp;
					pCur->next = p->next;
					p->next = pCur;
					break;
				}
				p = p->next;
			}
			if (pCurNext)
			{
				pCur = pCurNext;
			}
			else
			{
				pCur = NULL;
			}
			
		}
		return head;
	}
};
int main()
{
	ListNode  head[4];
	head[0].val = 4;
	head[1].val = 2;
	head[2].val = 1;
	head[3].val = 3;
	head[0].next = &head[1];
	head[1].next = &head[2];
	head[2].next = &head[3];
	head[3].next = NULL;
	Solution cS;
	ListNode * result = cS.insertionSortList(head);
	while (result)
	{
		cout<<result->val;
		result = result->next;
	}
	return 0;
}
           

自己寫得比較繁雜，看到别人寫得比較簡單，可以參考

class Solution
{
public:
	ListNode *insertionSortList(ListNode *head)
	{
		if(head==NULL || head->next==NULL) return head;
		ListNode *cur=head;
		ListNode *helper=new ListNode(0);
		ListNode *pre;
		while(cur)
		{
			ListNode *next=cur->next;
			pre=helper;
			while(pre->next!=NULL && pre->next->val<cur->val)
			{
				pre=pre->next;
			}
			cur->next=pre->next;
			pre->next=cur;
			cur=next;
		}
		return helper->next;
	}


};
           

建立了一個新的連結清單，把符合要求的節點一個個複制到這個新連結清單當中

利用pre節點創造了新的連結清單，一直是保持有個新的連結清單結構

pre->......->null

cur->......->null

while循環中就是比較cur對應的節點在pre當中的位置，或者直接到pre的最後面了，然後将cur直接插入進入pre對應的連結清單當中