รายการเรียงลำดับการแทรก C++

สมมติว่าเรามีรายการที่เชื่อมโยง เราต้องทำการเรียงลำดับการแทรกในรายการนี้ ดังนั้นหากรายการเป็นแบบ [9,45,23,71,80,55] รายการเรียงเป็น [9,23,45,55,71,80]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• dummy :=โหนดใหม่พร้อมค่าสุ่มบางส่วน

• โหนด :=รายการที่กำหนด

• ในขณะที่โหนดไม่เป็นโมฆะ

  • newNode =ถัดไปของโหนด dummyHead :=ถัดไปของ dummy prevDummyHead :=ดัมมี่

  • ในขณะที่เป็นจริง -

    • ถ้าไม่มี dummyHead ค่าของ dummyHead> ค่าของโหนด

      • ถัดไปของโหนด :=dummyHead

      • ถัดไปของ prevDummyHead :=โหนด

      • หมดห่วง

    • prevDummyHead :=dymmyHead และ dummyHead =ถัดจากส่วนหัวจำลอง

  • โหนด :=โหนดถัดไป

• กลับมาต่อจากดัมมี่

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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]