題目

給你一個連結串列的頭節點 head，請你編寫程式碼，反覆刪去連結串列中由 總和 值為 0 的連續節點組成的序列，

直到不存在這樣的序列為止。

你可以返回任何滿足題目要求的答案。

（注意，下面示例中的所有序列，都是對 ListNode 物件序列化的表示。）

示例 1：輸入：head = [1,2,-3,3,1] 輸出：[3,1]

提示：答案 [1,2,1] 也是正確的。

示例 2：輸入：head = [1,2,3,-3,4] 輸出：[1,2,4]

示例 3：輸入：head = [1,2,3,-3,-2] 輸出：[1]

提示：給你的連結串列中可能有 1 到 1000 個節點。

對於連結串列中的每個節點，節點的值：-1000 <= node.val <= 1000.

解題思路分析

1、雜湊輔助；時間複雜度O(n)，空間複雜度O(n)

func removeZeroSumSublists(head *ListNode) *ListNode {	m := make(map[int]*ListNode)	res := head	sum := 0	for cur := head; cur != nil; cur = cur.Next {		sum = sum + cur.Val		if sum == 0 { // 當前都為0			res = cur.Next			m = make(map[int]*ListNode)			continue		}		if _, ok := m[sum]; ok == false {			m[sum] = cur			continue		}		// 出現重複		first := m[sum]		tempSum := sum		for temp := first.Next; temp != cur; temp = temp.Next {			tempSum = tempSum + temp.Val			delete(m, tempSum)		}		first.Next = cur.Next	}	return res}

2、遍歷；時間複雜度O(n)，空間複雜度O(1)

func removeZeroSumSublists(head *ListNode) *ListNode {	res := &ListNode{Next: head}	for cur := res; cur != nil; {		sum := 0		for temp := cur.Next; temp != nil; temp = temp.Next {			sum = sum + temp.Val			if sum == 0 {				cur.Next = temp.Next // 調整指標			}		}		cur = cur.Next	}	return res.Next}

3、雜湊輔助；時間複雜度O(n)，空間複雜度O(n)

func removeZeroSumSublists(head *ListNode) *ListNode {	res := &ListNode{Next: head}	m := make(map[int]*ListNode)	sum := 0	for cur := res; cur != nil; cur = cur.Next {		sum = sum + cur.Val		m[sum] = cur	}	sum = 0	for cur := res; cur != nil; cur = cur.Next {		sum = sum + cur.Val		cur.Next = m[sum].Next	}	return res.Next}

4、遞迴；時間複雜度O(n^2)，空間複雜度O(n)

func removeZeroSumSublists(head *ListNode) *ListNode {	if head == nil {		return nil	}	sum := 0	for cur := head; cur != nil; cur = cur.Next {		sum = sum + cur.Val		if sum == 0 {			return removeZeroSumSublists(cur.Next)		}	}	head.Next = removeZeroSumSublists(head.Next)	return head}

總結

Medium題目，連結串列題目