LeetCode1171

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

语言：Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode result = new ListNode(0); //处理[0]、[0,0]、[1,-1]少于3个节点的情况
        result.next = head;

        HashMap<Integer, ListNode> hmap = new HashMap<>();
        int sum = 0;
        //建立sum <-> ListNode映射
        for (ListNode temp = result; temp != null; temp = temp.next) {
            sum += temp.val;
            hmap.put(sum, temp);
        }

        sum = 0;
        //如果连续区间内有两个节点的前缀和是相同的，那么区间的和为0
        for (ListNode temp = result; temp != null; temp = temp.next) {
            sum += temp.val;
            if(hmap.containsKey(sum)) {
                temp.next = hmap.get(sum).next;
            }
        }

        return result.next;
    }
}

语言 Golang：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeZeroSumSublists(head *ListNode) *ListNode {
    var mapx = make(map[int]*ListNode, 0)
    var r *ListNode = &ListNode{}
    r.Next = head
    var sum = 0
    for temp:= r; temp != nil; temp = temp.Next {
        sum += temp.Val
        mapx[sum] = temp
    }

    sum = 0;
    for temp := r; temp != nil; temp = temp.Next  {
          sum += temp.Val
          ele, ok := mapx[sum]
          if ok {
              temp.Next = ele.Next
          }
    }

    return r.Next
}