Giả sử ta có đầu (head) của một danh sách liên kết; ta phải lặp lại xóa các dãy liên tiếp của các nút có tổng bằng 0 cho đến khi không còn dãy nào như vậy. Sau khi làm xong, ta trả về đầu của danh sách liên kết cuối cùng. Ví dụ, nếu danh sách là [1,2,-3,3,1], kết quả sẽ là [3,1].
Để giải quyết, ta thực hiện các bước sau:
Tạo một nút giả (dummy) với giá trị 0, đặt next của dummy := head.
Tạo một map m, lưu dummy cho khóa 0 vào m, đặt sum = 0.
Khi head không null:
sum := sum + giá trị head, đặt m[sum] := head, và head := next của head.
head := dummy.
sum := 0.
Khi head không null:
sum := sum + giá trị head.
temp := m[sum].
Nếu temp khác head, thì next của head := next của temp.
head := next của head.
Trả về next của dummy.
Xem triển khai dưới đây để hiểu rõ hơn:
Ví dụ minh họa
#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* removeZeroSumSublists(ListNode* head) { ListNode* dummy = new ListNode(0); dummy->next = head; unordered_map <int, ListNode*> m; m[0] = dummy; int sum = 0; while(head){ sum += head->val; m[sum] = head; head = head->next; } head = dummy; sum = 0; while(head){ sum += head->val; ListNode* temp = m[sum]; if(temp != head){ head->next = temp->next; } head = head->next; } return dummy->next; } }; main(){ vector<int> v1 = {1,2,-3,3,1}; ListNode *head = make_list(v1); Solution ob; print_list(ob.removeZeroSumSublists(head)); }Đầu vào
[1,2,-3,3,1]
Kết quả
[3,1]