Leetcode - Remove Zero Sum Consecutive Nodes from Linked List

violet posted @ Jun 05, 2020 07:23:06 AM in 算法 with tags Algorithm Linked List Golang , 265 阅读

https://leetcode.com/problems/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.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeZeroSumSublists(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    hash := map[int]*ListNode{}
    node := head
    sum := 0
    for node != nil {
        sum += node.Val
        if sum == 0 {
            head = node.Next
        }
        if val, ok := hash[sum]; ok {
            tmp := sum
            n := val.Next
            for n != node {
                tmp += n.Val
                delete(hash, tmp)
                n = n.Next
            }
            hash[sum].Next = node.Next
            return removeZeroSumSublists(head)
        }
        hash[sum] = node
        node = node.Next
    }
    return head
}