[Leetcode] 1171. Remove Zero Sum Consecutive Nodes from Linked List (Medium)

概述

題目

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
給出一個 Linked List，問經過刪去所有隨意數組合為 0 之最後結果

心得

刪掉組合為 0 的數集合，可透過 Hash + Pre Sum 來解

Hash + Pre Sum

思路

from zzhuaixin，基本資料的建立都如題意所述，維 get 時加入 Binary Search 的操作以增加效率

程式

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeZeroSumSublists(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode()
        dummy.next = head
        pre = 0
        dic = {}
        dic[0] = dummy

        # 記錄 Pre Sum 狀態，提供捷徑的概念
        while head != None:
            pre += head.val
            dic[pre] = head
            head = head.next
        
        head = dummy
        pre = 0
        
        # 有捷徑就跳，且是往最後一次相同 Pre Sum 的出口跳
        while head != None:
            pre += head.val
            head.next = dic[pre].next
            head = head.next
        
        return dummy.next

from ashar0706，只 traverse 一次，一旦發生有捷徑即馬上更新之前路徑

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeZeroSumSublists(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dic = {}
        pre = 0
        dummy = head
        while dummy != None:
            pre += dummy.val

            # 發現有零的狀況直接將下個 node 當作起點，過往全部跳掉
            if pre == 0:
                head = dummy.next
            else:
            	# 沒來過就當捷徑起點
                if pre not in dic:
                    dic[pre] = dummy

                # 有走過就是捷徑終點，直接將捷徑往後拉
                else:
                    dic[pre].next = dummy.next
            dummy = dummy.next
        return head

Complexity

Time Complexity: O(n)
走過所有 Linked List 兩次或只有一次，故為 O(n)

Space Complexity: O(n)
Hash Table 最多記錄 n 個 ListNode 位置 / 資訊

Stack

思路

from jainsiddharth99，透過 Stack 將組合為 0 的數組刪去

程式

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeZeroSumSublists(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        arr = []
        dummy = head

        # 取出數組
        while dummy != None:
            if dummy.val != 0:
                arr.append(dummy.val)
            dummy = dummy.next

        n = len(arr)

        # 透過 Stack 方式將合為 0 之組合拿掉
        stk = []
        for c in arr:
            if len(stk) != 0:
                tot = c
                for i in range(len(stk)-1, -1, -1):
                    tot += stk[i]
                    if tot == 0:
                        stk = stk[:i]
                        break
                else:
                    stk.append(c)

            else:
                stk.append(c)

        # 重建 Linked List
        dummy = ListNode(0)
        res = dummy
        for c in stk:
            dummy.next = ListNode(c)
            dummy = dummy.next
        return res.next