假设我们有一个链接列表,我们必须对该列表执行插入排序。因此,如果列表类似于[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
返回假人的下一个
让我们看下面的实现以更好地理解-
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; }
[9,45,23,71,80,55]
输出结果
[9,23,45,55,71,80]