插入排序列表C ++

假设我们有一个链接列表,我们必须对该列表执行插入排序。因此,如果列表类似于[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]