2020-06-06

技术博客

38 分钟读完 (大约 5629 个字) 0次访问

算法题（四）

非科班出身，在校时没写过算法题，因此特做专题收录。

算法题我会偏向于python和go，说不定也会用java和js写一些，暂时不想用c++，也不会用php（只用它写web）

链表

Python实现链表的常用形式是ListNode类。

从头到尾打印链表

获得一个链表的起始结点，即相当于获得了整个链表的所有结点的所有值。

def print_linked_list(head):
    """
    打印链表
    :param head: 要打印的链表的头结点
    :return: 结点值列表
    """
    tmp = head              # 临时变量
    nums = []
    while tmp:
        nums.append(tmp.val)
        tmp = tmp.next
    print(nums)
    return nums

上述情况适用于非环形链表的情况

链表复制

链表复制相当于链表的浅拷贝，在链表题目中可以避免链表进入函数后被修改等情况。

def copy_linked_list(head):
    """
    把链表复制一份，且不改变原链表结构
    :param head:
    :return:
    """
    new_head, cur = ListNode(0), head       # 新链表的准头结点，原来链表的当前结点
    tmp = new_head                          # 临时结点
    while cur:                              # 当前结点不为空
        new_cur = ListNode(cur.val)         # 根据原链表当前结点构造新的当前结点
        tmp.next = new_cur                  # 新结点连接到已完成的部分末尾
        cur = cur.next                      # 当前结点后移
        tmp = tmp.next                      # 新链表末尾后移
    return new_head.next                    # 返回新链表

两数相加(2)

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

例：输入：L1 = [2,4,3], L2 = [5,6,4]

输出：[7,0,8],342+465=807

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        num1 = ''
        num2 = ''
        while l1:
            num1 += str(l1.val)
            l1 = l1.next
        while l2:
            num2 += str(l2.val)
            l2 = l2.next
        add = str(int(num1[::-1]) + int(num2[::-1]))[::-1]
        head = ListNode(add[0])
        answer = head
        for i in range(1, len(add)):
            node = ListNode(add[i])
            head.next = node
            head = head.next
        return answer

两数相加2(445)

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        num1 = ''
        num2 = ''
        while l1:
            num1 += str(l1.val)
            l1 = l1.next
        while l2:
            num2 += str(l2.val)
            l2 = l2.next
        add = str(int(num1) + int(num2))
        head = ListNode(add[0])
        answer = head
        for i in range(1, len(add)):
            node = ListNode(add[i])
            head.next = node
            head = head.next
        return answer

删除单链表中倒数第K个节点(19)

设置两个指针，快指针比慢指针提前k个单元，当快指针到达单链表尾部时，慢指针指向待删除节点的前节点。

def delete_n(linkList, n):
    p = linkList.head
    q = linkList.head
    while n:
        q = q.next
        n -= 1
    # 删除第一个元素
    if q == 0:
        linkList.head = linkList.head.next
    else:
        while q.next != 0:
            p = p.next
            q = q.next
        if q.next == 0:
            p.next = p.next.next

合并两个有序链表21

递归

def Merge(self,pHead1,pHead2):
    if not pHead1:
        return pHead2
    if not pHead2:
        return pHead1
    if pHead1.val <= pHead2.val:
        pHead1.next = self.Merge(pHead1.next,pHead2)
        return pHead1
    else:
        pHead2.next = self.Merge(pHead1,pHead2.next)
        return pHead2

合并K个升序链表(23)

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        stack = []
        for singleNode in lists:
            while singleNode:
                stack.append(singleNode.val)
                singleNode = singleNode.next
        resNode = tem = ListNode(0)
        stack.sort()
        for a in stack:
            tem.next = ListNode(a)
            tem = tem.next
        return resNode.next

两两交换链表中的节点(24)

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

例：输入：head=[1,2,3,4]

输出：[2,1,4,3]

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        tail = head.next
        head.next = self.swapPairs(tail.next)
        tail.next = head
        return tail

链表相交(160)

编写一个程序，找到两个单链表相交的起始节点。

1 2	class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:

p1 = headA
p2 = headB
while (p1 != p2)
     p1 = headB if p1 == None else p1.next
     p2 = headA if p2 == None else p2.next
return p1

对链表进行插入排序(147)

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if(head==None or head.next==None):
            return head
        else:
            h=ListNode();h.next=head;
            ##  增设一个头指针，使得操作一致。
            p=head.next;head.next=None
            ##  第一个节点不用排序，和后面的节点断开；p指向未排序链表的第一个节点
            s=h;st=h.next
            ##  利用插入法进行链表排序。增设两个指针，s和st。
            ##  st指向要与p进行比较的节点，s指向st的前一个节点
            while(p!=None):
                if(p.val<s.val):
                    s=h;st=h.next       ##  利用上次排序的结果;以减少比较次数
                
                while(st!=None and p.val>st.val):
                    s=st;st=st.next
                ##  已经找到位置，进行插入
                s.next=p;p=p.next;s.next.next=st;s=s.next
                
            return h.next

链表排序(148)

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

例：输入：head = [3,4,1,2]

输出：[1,2,3,4]

归并排序

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        head1 = slow.next
        slow.next = None
        left, right = self.sortList(head), self.sortList(head1)
        dummy = cur = ListNode(0)
        while left and right:
            if left.val < right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        if left:cur.next = left
        if right:cur.next = right
        return dummy.next

环形链表141

给定链表，判断链表入环的节点

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

快慢指针

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head == None or head.next == None:
            return False
        slow = head
        fast = head.next
        while slow != fast:
            if fast == None or fast.next == None:
                return False
            fast = fast.next.next
            slow = slow.next
        return True

环形链表142

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

例：输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点

同样是快慢指针

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if head is None:
            return None
        if head.next is None:
            return None
        first = second = head
        while second.next and second.next.next:
            first = first.next
            second = second.next.next
            if first == second:
                p = head
                while first != p:
                    p = p.next
                    first = first.next
                return p
        return None

判断是否是环形链表

def is_circle(head):
    """
    判断链表是否是环形链表
    :param head: 要判断的链表的头结点
    :return: 布尔量，判断结果
    """
    if not head:
        return False
    tmp = head

    while head:
        head = head.next
        if not head:        # 遍历到了链表末尾
            return False    # 链表不是环形结点
        if head == tmp:     # 遍历到了之前遍历过的结点
            return True     # 链表是环形结点

反转链表206

输入：1->2->3->4->5->NULL

输出：5->4->3->2->1->NULL

不改变链表的值，改变链表指针的指向来满足题目要求

迭代，并行赋值

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        p,rev = head,None
        while p:
           rev,rev.next,p = p,rev,p.next
        return rev

递归

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        //判断当前节点和下一节点是否为空节点，不为空进入递归
        if not head:
            return None
        if not head.next:
            return head
        headNode = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return headNode

通过self.reverseList(head.next)语句进入递归，链表的会一直往后传递，直到找到最后一个节点，此时5节点的next节点为null，返回head，则5节点为头部。

进入上一层递归之后，head节点为4，指向还没改变之前节点4的head.next.next指向null，head.next指向5节点，head.next.next = head语句将原来指向None的节点5，改为指向节点4，完成5->4,head.next = None 语句完成4->none,也就完成了5-4-none

其他依次类推，直到反转所有节点。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        //判断当前节点和下一节点是否为空节点，不为空进入递归
        if not head:
            return None
        if not head.next:
            return head
        headNode = reverseList(head.next)
              def reverseList(self, head: ListNode) -> ListNode:
                  //判断当前节点和下一节点是否为空节点，不为空进入递归
                  if not head:
                      return None
                  if not head.next:
                      return head
                  headNode = self.reverseList(head.next)
                          def reverseList(self, head: ListNode) -> ListNode:
                          //判断当前节点和下一节点是否为空节点，不为空进入递归
                          if not head:
                              return None
                          if not head.next:
                              return head
                          headNode = self.reverseList(head.next)
                              def reverseList(self, head: ListNode) -> ListNode:
                                //判断当前节点和下一节点是否为空节点，不为空进入递归
                                if not head:
                                    return None
                                if not head.next:
                                    return head
                                headNode = self.reverseList(head.next)
                                        def reverseList(self, head: ListNode) -> ListNode:
                                        //判断当前节点和下一节点是否为空节点，不为空进入递归
                                        if not head:
                                            return None
                                        if not head.next:
                                            return head
                                head.next.next = head
                                head.next = None
                                return headNode
                          head.next.next = head
                          head.next = None
                          return headNode
                  head.next.next = head
                  head.next = None
                  return headNode
        head.next.next = head
        head.next = None
        return headNode

反转链表2(92)

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

例：输入：head = [1,2,3,4,5],left = 2,right = 4

输出：[1,4,3,2,5]

找到要翻转的部分进行翻转，翻转之后进行拼接

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if m == n:
            return head
        //留下头节点，方便操作
        dummy = ListNode(0)
        dummy.next = head
        p = dummy
        //留下指针
        for i in range(m - 1):
            p = p.next
        prev = p
        curr = p.next
        tail = curr
        //翻转要操作的部分
        for i in range(n - m + 1):
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        //连接节点
        p.next = prev
        tail.next = curr
        return dummy.next

还有创建数组再压入栈(使用新空间)、逐个前插法

两两交换链表节点24

改变节点指向或者改变两个节点的值，如果不给定常数的额外空间则修改指向

class Solution(object):  
  //修改值
  def swapPairs(self, head):
        p = head
        while p is not None and p.next is not None:
            tmp = p.val
            p.val = p.next.val
            p.next.val = tmp
            p = p.next.next
        return head
  //修改指向
  def swapPairs(self, head): 
      if head == None:
        return head
      cur = ListNode(0)
      cur.next = head
      first =cur
      while cur.next and cur.next.next:
        n1 = cur.next
        n2 = n1.next
        nxt = n2.next
        n1.next = nxt
        n2.next = n1
        cur.next = n2

        cur = n1
        return first.next

K个一组列表翻转(25)

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

例：输入：head=[1,2,3,4,5]，k=3

输出：[3,2,1,4,5]

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        cur = head
        count = 0
        while cur and count!= k:
            cur = cur.next
            count += 1
        if count == k:
            cur = self.reverseKGroup(cur, k)
            while count:
                tmp = head.next
                head.next = cur
                cur = head
                head = tmp
                count -= 1
            head = cur   
        return head

移除链表指定元素(203)

移除链表中的指定元素

例：链表1->2->6->3->4->5->6 指定删除元素 val=6

输出结果 1->2->3->4->5

定义两个临时变量：

伪头节点pre_head：用于处理头结点即为要删去的情况；将输入的头结点挂在该结点上，作为整个链表的前序结点，

当前节点cur：用于迭代遍历和删除结点元素。

class Solution(object):
    def removeElements(self, head, val):
        cur = pre_head = ListNode(0)            # 定义一个辅助结点
        pre_head.next = head                    # 把输入链表挂在该结点上

        while cur.next:                         # 当前结点不是最后一个结点时
            if cur.next.val == val:             # 如果下一个结点的值是要删除的
                cur.next = cur.next.next        # 删除下一个结点
            else:                               # 否则
                cur = cur.next                  # 当前结点后移
        return pre_head.next                    # 返回处理后的链表

删除链表中的节点(237)

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

输入：head = [4,5,1,9], node = 5

输出：[4,1,9]

class Solution:
    def deleteNode(self, node):
        # 因为无法访问前一个结点，所以可以把要删除的结点的后一个结点的值前移
        node.val = node.next.val;
        # 然后删除掉后一个结点
        node.next = node.next.next;

旋转链表61

给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中k是非负数

例：输入：1->2->3->4->5->Null,K=2

输出：4->5->1->2->3->Null,

首尾相连，然后计算需要走到有效步数，在对应位置断开即可。

class Solution: 
   def rotateRight(self,head:ListNode,k:int)->ListNode:
       if not head: return None
        orig_head, cnt = head, 1 #cnt如果会遍历到none，就从0开始计数（右开空间），如果遍历到最后有效位，就从1开始（右闭空间）
        while head.next:                # head遍历到了最后一位
            head, cnt = head.next, cnt+1# cnt若从1开始，且紧跟着head，那么pointer最终停到哪，cnt就包括到哪。是完全相同的
        head.next = orig_head           # 首尾连接上

        step = cnt - k % cnt-1          # 计算有效移动步数
        while step > 0:
            orig_head, step = orig_head.next, step - 1
        
        new_head, orig_head.next = orig_head.next, None
        return new_head

删除排序链表中的重复元素(83)

如果排序链表中所有重复出现次数的元素，删除重复元素到没有重复，只保留一个元素，不指定值，

例：

链表1->2->3->3->4->5->6 输出结果 1->2->3->4->5->6

链表1->1->1->4->5->6 输出结果 1->4->5->6

设置一个替代指针，同替代进行修改操作。对于每个cur，将其与其后继的节点值比较，如果相同，说明这个后继需要删除，对链表而言，操作则相当简单，直接将cur的后继改为当前后继的后继即可。如果不同，说明没有与当前节点值重复的了，直接将当前节点后移即可，

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
      # 判断链表是否为空
        if not head:
            return head
          # 当前节点初始化为表头
        cur = head
        while cur and cur.next:# 遍历，循环条件为当前节点和当前节点的后继不为空
            if cur.val == cur.next.val:# 如果当前节点值和其后继值相等，则将其后继改为后继的后继
                cur.next = cur.next.next# 如果不相等，则将当前节点更新
            else:
                cur = cur.next
        return head

删除重复元素2(82)

如果排序链表中所有重复出现次数的元素，删除全部重复元素，不指定值，

例：输入: 1->2->3->3->4->4->5
输出: 1->2->5

比上一版难度加在：头部可能会被删除；如果出现重复元素全部删除，可能断链

思路：设置两个指针，一个保存表头，一个替代进行遍历。遍历的思路：如果发现重复元素，不能直接替换，需要向后移动，直到找到不重复元素，将其替换

class Solution:
  def deleteDuplicates(self, head: ListNode) -> ListNode:
        #判断链表是否为空
        if not head:
            return head
        pre = None# 设置两个指针：pre和cur
        cur = head
        # 遍历所有节点
        while cur:
            # 一个临时指针指向cur的后继
            _next = cur.next
            if not _next:
                return head
            # 如果两个值不相等，则将pre和cur都往后移
            elif cur.val != _next.val:
                pre = cur
                cur = _next
                continue
            # 如果相等，则将_next一直捋到不重复为止
            else:
                while _next and _next.val == cur.val:
                    _next = _next.next
                if cur == head:# 如果重复段在表头，则需要更新表头信息
                    head = _next
                else:# 如果重复段在中间，则需要将pre的后继更新为_next
                    pre.next = _next
                # 继续遍历
                cur = _next
        return head

分隔链表(86)

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

例：输入：head = [1,4,3,2,5,2],x = 3

输出：[1,2,2,4,3,5]

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        dummy1 = ListNode(0)
        dummy2 = ListNode(0)
        p1, p2 = dummy1, dummy2
        cur = head
        while cur:
            if cur.val < x:
                p1.next = cur
                p1 = p1.next
            else:
                p2.next = cur
                p2 = p2.next
            #print(cur.val)
            cur = cur.next
        p2.next = None
        p1.next = dummy2.next
        return dummy1.next

重排链表(143)

给定一个单链表 L：L0→L1→…→L**n-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→L**n-2→…

例：给定链表 1->2->3->4, 重新排列为 1->4->2->3.

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head or not head.next: return head
        fast, slow = head, head
        #找到中点
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        #反转后半链表
        p, right = slow.next, None
        slow.next = None
        while p:
            right, right.next, p = p, right, p.next
        #重排练表
        left = head
        while left and right:
            left.next,right.next,left,right = right,left.next,left.next,right.next

两个链表的第一个公共节点(剑指offer52)

输入两个链表，找出它们的第一个公共节点。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A, B = headA, headB
        while A != B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A

回文链表(234)

请判断一个链表是否为回文链表。

例：输入：1->2->2->1

输出：true

转数组，时间复杂度和空间复杂度都是O(n)

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        a = []
        while head is not None:
            a.append(head.val)
            head = head.next
        for i in range(len(a)):
            if a[i] != a[-1-i]:
                return False
        return True

利用快慢指针将后半部分翻转，然后进行比较，O(n) 时间复杂度和 O(1) 空间复杂度

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head:
            return True
        slow = fast = head
        pre = None
        # 快指针指向下两个，这样遍历之后，slow只走到中间节点，同时翻转后半部分链表
        while fast and fast.next:
            fast = fast.next.next
            slow.next, pre, slow = pre, slow , slow.next
        if fast:
            slow = slow.next
        #进行比较
        while pre:
            if pre.val != slow.val:
                return False
            pre = pre.next
            slow = slow.next
        return True

奇偶链表(328)

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

例：输入：2->1->3->5->6->4->7->NULL

输出：2->3->6->7->1->5->4->NULL

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if head == None: return head
        point1, point2 = head, head.next
        p1, p2 = point1, point2
        while p2 != None and p2.next:
           p1.next = p1.next.next
           p2.next = p2.next.next
           p1 = p1.next
           p2 = p2.next
        p1.next = point2
        return point1

分隔链表(725)

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

例：输入：root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3

输出：[[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

class Solution:
    def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
        total_len = 0
        head = root
        while head:
            total_len += 1
            head = head.next
        
        ans = [None for _ in range(k)]
        
        l, r = total_len // k, total_len % k
        
        prev, head = None, root
        
        for i in range(k):
            ans[i] = head
            for j in range(l + (1 if r > 0 else 0)):
                prev, head = head, head.next
            if prev: prev.next = None
            r -= 1
        
        return ans

链表中的下一个更大节点(1019)

给定一个链表，返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1})

例：输入：[2,7,4,3,5]

输出：[7,0,5,5,0]

输入：[1,7,5,1,9,2,5,1]

输出：[7,9,9,9,0,5,0,0]

class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        if not head:
            return []
        nums = []
        cur = head
        while cur:
            nums.append(cur.val)
            cur=cur.next
        stack = [0]
        res = [0]*len(nums)
        for i in range(1,len(nums)):
            while stack and nums[i]>nums[stack[-1]]:
                res[stack[-1]]=nums[i]
                stack.pop()
            stack.append(i)
        return res

从链表中删去总和值为零的连续节点(1171)

给你一个链表的头节点 head，请你编写代码，反复删去链表中由总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

例：输入：[1,2,3,-3,4]

输出：[1,2,4]

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        fake_head = ListNode(0)
        fake_head.next = head

        sum_map = dict()
        p, sum_value = fake_head, 0
        while p:
            sum_value += p.val
            sum_map[sum_value] = p
            p = p.next
        p, sum_value = fake_head, 0
        while p:
            sum_value += p.val
            p.next = sum_map[sum_value].next
            p = p.next
        return fake_head.next

# IT,Web，算法