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 vào danh sách này. Vì vậy, nếu danh sách giống như [9,45,23,71,80,55], danh sách được sắp xếp là [9,23,45,55,71,80].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
dummy:=new Node với một số giá trị ngẫu nhiên
-
node:=danh sách đã cho
-
trong khi nút không rỗng,
-
newNode =next of node, dummyHead:=next of dummy, presDummyHead:=dummy
-
trong khi đúng -
-
nếu không có dummyHead, giá trị của dummyHead> giá trị của nút
-
tiếp theo của nút:=dummyHead
-
tiếp theo của presDummyHead:=node
-
phá vỡ vòng lặp
-
-
presDummyHead:=dymmyHead, và dummyHead =tiếp theo của đầu giả
-
-
nút:=nextNode
-
- trở lại tiếp theo của hình nộm
Ví dụ
Hãy cùng chúng tôi xem cách 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; }
Đầu vào
[9,45,23,71,80,55]
Đầu ra
[9,23,45,55,71,80]