C ++中的插入排序列表

  • Z时代
  • 2024-01-10
  • 分类：综合

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

    以上是 C ++中的插入排序列表 的全部内容， 来源链接： utcz.com/z/338329.html

    回到顶部