1171从链表中删除总和值为0的连续节点

1171. 从链表中删去总和值为零的连续节点

下面是题目,需要注意的是，题目说的是总和为0的连续结点

下面是题目给出的模板

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {

    }
};

昨天只看了题解，还是没看懂，今天自己解了一边，再看题解，发现了几个细节点值得注意

/*
	这题的原理很简单，就是通过记录序列和，来达到判断是否要删除节点
	比如拿1，2，3，-3，4来说
	其序列和就是1，3，6，3，7
	我们看见第二个和第四个是相同的，说明3，4的两个节点的和为0，我们要做一个对3，4的删除
	那么如何能做到这个删除呢？其实用无序图存储数据即可
*/
class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        //这里是第一个小细节，我们要用无序图来存储，否则会打乱我们存储的数据顺序
        unordered_map<int,ListNode*>mp;
        //因为头节点可能会被删除，所以我们要用哑头节点
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *p = dummy;
        int val ;
        //这里是第二个小细节，也是我们一定要养成的习惯，就是能初始化的就要初始化！
        mp[0] = p;//对于图中第一个元素，先把哑节点存储进去
        int curval=0,tempval=0;
        //这里需要定两个值，一个来记录当前的序列和，并且做存储，一个用来删除节点
        //然后就开始迭代
        while(p=p->next)//p = p->next这句话在，就不用在循环的最后写p=p->next了
        {
            //curval用来计算序列和
            curval+=p->val;
            //因为图中只能存储相同的键值，所以，如果重复的话，mp.find(curval)就不会返回end()
            if(mp.find(curval)!=mp.end())//所以把这个当作判定条件
            {
            //这里，我们仍然用1 2 3 -3 4 来做判断
         	//前三个节点和为1，3，6，都已经存储在map中，现在的curval又等于3，所以执行此操作
            //这时候，先定义一个temp数组，让他指向第mp[3]的后一个节点，也就是第三个节点3
                ListNode* temp = mp[curval]->next;
            //然后用mp[3]节点指向当前p节点的下一个节点，也就是第五个节点4，从而实现1，2，4相连，并删除中间的两个节点
                mp[curval]->next= p->next;
				//但是，光节点指一下是不够的，mp[6]仍然在图中，如果下面的节点还是3，岂不是也要被删除？所以，为了避免这种干扰，我们要将mp[6]删除！怎么删除呢，tempval和temp节点的作用就在此 
                tempval=curval；//这时，tempval = 3
                while(temp!=p)//判断条件就是，temp节点到p节点之间存储在mp中的项全部删光
                    //因为这时候p节点还没有入图，所以不用删除
                {
                    //现在经过下一步操作tempval = 6
                    tempval += temp->val;
                    //然后移除mp中所有的，key值为6的项，（其实只有一项，mp中的key不可以重复）
                    mp.erase(tempval);
                    //继续
                    temp=temp->next;
                }
            }else//如果这个序列和没有在图内找到，说明是个新的序列和，把他加入到图中
            {
                mp[curval]=p;
            }
             
        }
        return dummy->next;
    }
};