Sắp xếp chèn danh sách liên kết trong C++

Giả sử chúng ta có một danh sách liên kết, chúng ta phải thực hiện sắp xếp chèn (insertion sort) trên danh sách này. Ví dụ, nếu danh sách là [9,45,23,71,80,55], danh sách đã sắp xếp sẽ là [9,23,45,55,71,80].

Để giải quyết, ta thực hiện các bước sau:

• dummy := nút mới với giá trị ngẫu nhiên
• node := danh sách cho trước
• while node không null
  • newNode = next của node, dummyHead := next của dummy, prevDummyHead := dummy
  • while true
    • if dummyHead không tồn tại, giá trị của dummyHead > giá trị của node
      • next của node := dummyHead
      • next của prevDummyHead := node
      • thoát vòng lặp
    • prevDummyHead := dummyHead, và dummyHead = next của dummy head
  • node := nextNode
• return next của dummy

Ví dụ

Hãy xem triển khai sau để hiểu rõ hơn:

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; }

Input

[9,45,23,71,80,55]

Output

[9,23,45,55,71,80]