Loại bỏ số tổng bằng không các mã liên tiếp khỏi danh sách được liên kết trong C ++

Giả sử chúng ta đã đưa ra phần đầu của một danh sách được liên kết; chúng ta phải xóa nhiều lần các chuỗi nút liên tiếp có tổng bằng 0 cho đến khi không còn chuỗi nào như vậy. Vì vậy, sau khi làm như vậy, chúng ta phải trả lại phần đầu của danh sách liên kết cuối cùng. Vì vậy, nếu danh sách giống như [1,2, -3,3,1], thì kết quả sẽ là [3,1].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một nút có tên là dummy và lưu trữ 0 vào đó, đặt bên cạnh của dummy:=head

• tạo một bản đồ m, lưu trữ giả cho khóa 0 thành m, đặt sum =0

• trong khi head không rỗng -

  • sum:=sum + giá trị của head, đặt m [sum]:=head và head:=next of head

• head:=dummy

• tổng:=0

• trong khi đầu không rỗng

  • sum:=sum + giá trị của head

  • tạm thời:=m [sum]

  • nếu tạm thời không phải là đầu, thì tiếp theo của đầu:=tiếp theo của tạm thời

  • head:=next of head

• trở lại tiếp theo của hình nộm

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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]

Đầu ra

[3,1]