1171.md

Remove Zero Sum Consecutive Nodes from Linked List

题目

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1: Input: head = [1,2,-3,3,1] Output: [3,1] Note: The answer [1,2,1] would also be accepted.

Example 2: Input: head = [1,2,3,-3,4] Output: [1,2,4]

Example 3: Input: head = [1,2,3,-3,-2] Output: [1]

Constraints:

The given linked list will contain between 1 and 1000 nodes. Each node in the linked list has -1000 <= node.val <= 1000.

思路

总结：
	指针空间大小总归是八位，只是指向的是什么类型而已。
	从值为x开始经过了n次加法(加正数或者负数)如果还是为x，那么表示n次加法的和为0
part1：
	给链表加上一个头结点，该头结点的next即为题目给的head，初始化pre为头结点，cur为题给的head
	初始化一个map[int]*ListNode, value为链表的某个指针，key为从表头到value所表示的指针值的和的。
part2：
	遍历一边链表，cur表示遍历的当前结点。如果值为零使用pre和cur删除改值。更新对应指针。
	如果当前sum值在map存在，ptr=map[sum].next，ptr到cur(不包括cur)所对应的key。
	因为有ptr和sum的值，所以是可以做到上述操作的。

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeZeroSumSublists(head *ListNode) *ListNode {
    pre := &ListNode{0, head}
    head = pre
    mp := map[int]*ListNode{0: head}
    sum := 0
    for cur := pre.Next; cur != nil; cur = cur.Next {
        if cur.Val == 0 {
            pre.Next = cur.Next
            continue
        }
        sum += cur.Val
        if _, ok := mp[sum]; ok {
            ptr := mp[sum]
            pre = ptr
            tmpSum := sum
            for delPtr := ptr.Next; delPtr != cur; delPtr = delPtr.Next {
                tmpSum += delPtr.Val
                delete(mp, tmpSum)
            }   
            ptr.Next = cur.Next
        } else {
            mp[sum] = cur
            pre = cur
        }      
    }
    return head.Next
}