假设我们有一个链表,我们必须对该表执行插入排序。因此,如果列表类似于[9,45,23,71,80,55],则排序后的列表为[9,23,45,55,71,80]。
为了解决这个问题,我们将遵循以下步骤-
dummy:=具有一些随机值的新节点
节点:=给定列表
虽然node不为null,
如果不存在dummyHead,则dummyHead的值>节点的值
prevDummyHead:= dymmyHead,dummyHead =虚拟头的下一个
节点的下一个:= dummyHead
prevDummyHead的下一个:=节点
打破循环
newNode =节点的下一个,dummyHead:=下一个虚拟,prevDummyHead:=假
虽然为真-
节点:= nextNode
返回假人的下一个
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class ListNode{ public: int val; ListNode *next; ListNode(int data){ val = data; next = NULL; } }; ListNode *make_list(vector<int> v){ ListNode *head = new ListNode(v[0]); for(int i = 1; i<v.size(); i++){ ListNode *ptr = head; while(ptr->next != NULL){ ptr = ptr->next; } ptr->next = new ListNode(v[i]); } return head; } void print_list(ListNode *head){ ListNode *ptr = head; cout << "["; while(ptr){ cout << ptr->val << ", "; ptr = ptr->next; } cout << "]" << endl; } class Solution { public: ListNode* insertionSortList(ListNode* a) { ListNode* dummy = new ListNode(-1); ListNode* node = a; ListNode* nextNode; ListNode* dummyHead; ListNode* prevDummyHead; while(node != NULL){ nextNode = node->next; dummyHead = dummy->next; prevDummyHead = dummy; while(1){ if(!dummyHead || dummyHead->val > node->val){ node->next = dummyHead; prevDummyHead->next = node; //cout << prevDummyHead->val << " " << node->val << endl; break; } prevDummyHead = dummyHead; dummyHead = dummyHead->next; } node = nextNode; } return dummy->next; } }; main(){ vector<int> v = {5,3,2,0,-4,7}; ListNode *head = make_list(v); Solution ob; print_list(ob.insertionSortList(head)); }
{5,3,2,0,-4,7}
输出结果
[-4, 0, 2, 3, 5, 7, ]