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

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

/*
 * @lc app=leetcode.cn id=1171 lang=typescript
 *
 * [1171] 从链表中删去总和值为零的连续节点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function removeZeroSumSublists(head: ListNode | null): ListNode | null {}
// @lc code=end

解法 1: 模拟

function removeZeroSumSublists(head: ListNode | null): ListNode | null {
  let arr: ListNode[] = []
  while (head) {
    arr.push(head)
    head = head.next
  }
  while (arr.length) {
    const map = new Map<number, number>()
    map.set(0, -1)
    let [l, r] = [-1, -1],
      sum = 0
    for (let i = 0; i < arr.length; i++) {
      sum += arr[i].val
      if (map.has(sum)) {
        if (r === -1 || i - map.get(sum)! > r - l) {
          r = i
          l = map.get(sum)!
        }
      } else {
        map.set(sum, i)
      }
    }
    if (r === -1) break
    arr = arr.filter((v, i) => i <= l || i > r)
  }
  const root = arr[0] ?? null
  for (let i = 1; i < arr.length; i++) {
    arr[i - 1].next = arr[i]
  }
  if (arr.length) arr[arr.length - 1].next = null
  return root
}

解法 2: 一次遍历

function removeZeroSumSublists(head: ListNode | null): ListNode | null {
  let arr: ListNode[] = []
  while (head) {
    arr.push(head)
    head = head.next
  }
  const map = new Map<number, number>()
  map.set(0, -1)
  let interval: [number, number][] = [],
    sum = 0
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i].val
    if (map.has(sum)) {
      const l = map.get(sum)!,
        r = i
      let j = interval.length - 1
      while (j >= 0 && interval[j][0] >= l) j--
      if (j === -1 || interval[j][1] <= l) {
        while (interval.length && interval.length > j + 1) interval.pop()
        interval.push([l, r])
      }
    }
    map.set(sum, i)
  }
  const del: number[] = []
  for (let [l, r] of interval) {
    for (let i = l + 1; i <= r; i++) {
      del[i] = 1
    }
  }

  let root: ListNode | null = null
  let pre: ListNode | null = null
  for (let i = 0; i < arr.length; i++) {
    if (del[i] || !arr[i].val) continue
    if (!root) {
      root = arr[i]
      pre = root
    } else {
      pre.next = arr[i]
      pre = pre.next
    }
  }
  if (pre) pre.next = null

  return root
}

Case

test.each([
  { input: { head: [1, 2, -3, 3, 1] }, output: [3, 1] },
  { input: { head: [1, 2, 3, -3, 4] }, output: [1, 2, 4] },
  { input: { head: [1, 2, 3, -3, -2] }, output: [1] },
])('input: head = $input.head', ({ input: { head }, output }) => {
  const arr = LinkedList.serialize(removeZeroSumSublists(LinkedList.deserialize(head)))
  let flag = false
  const map = new Set([0])
  let sum = 0
  for (let num of arr) {
    sum += num
    if (map.has(sum)) {
      flag = true
      break
    } else {
      map.add(sum)
    }
  }
  expect(flag).toBe(false)
})