C++의 연결 목록에서 제로섬 연속 노드 제거

연결 목록의 머리 부분을 지정했다고 가정합니다. 그러한 시퀀스가 ​​없을 때까지 합이 0인 연속적인 노드 시퀀스를 반복적으로 삭제해야 합니다. 따라서 그렇게 한 후에 최종 연결 목록의 머리를 반환해야 합니다. 따라서 목록이 [1,2,-3,3,1]과 같으면 결과는 [3,1]이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• dummy라는 노드를 만들고 여기에 0을 저장하고 dummy :=head

  다음으로 설정합니다.

• 하나의 맵 m을 만들고 키 0에 대한 더미를 m에 저장하고 합계 =0으로 설정

• 머리가 null이 아닌 동안 -

  • sum :=sum + head 값, m[sum] :=head, head :=head 다음으로 설정

• 머리 :=더미

• 합계 :=0

• 머리가 null이 아닌 동안

  • 합계 :=합계 + 헤드 값

  • 온도 :=m[합계]

  • temp가 head가 아니면 head의 다음 :=temp의 다음

  • head :=머리 다음

• 더미 다음으로 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

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

입력

[1,2,-3,3,1]

출력

[3,1]