leetcode
March 12, 2024

Viiisit [LeetCode] - 1171. Remove Zero Sum Consecutive Nodes from Linked List

#php#javascript#ruby

keep learning, keep coding!

Problem - 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.)

翻譯蒟蒻

給定一個 Linked List 的 head ，需要重複刪除連續節點總和為 0 的序列，直到沒有這樣的序列存在為止。

利用一個 Map 來跟蹤節點的總和，並在遍歷 Linked list 時檢查是否存在和為零的連續節點。如果存在，則將這些節點從鏈表中移除。

Solution - JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var removeZeroSumSublists = function(head) {
  let map = new Map();
  let dummy = new ListNode(0);
  dummy.next = head;
  let sum = 0;
  let fast = dummy;
  let slow = head;
  while (slow) {
    sum += slow.val;
    map.set(sum, slow);
    slow = slow.next;
  }

  sum = 0;
  while (fast) {
    sum += fast.val;
    if (map.has(sum)) {
      fast.next = map.get(sum).next;
    }
    fast = fast.next;
  }
  return dummy.next;
};

Solution - Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def remove_zero_sum_sublists(head)
  hash = {}
  dummy = ListNode.new(0)
  dummy.next = head
  sum = 0
  fast = dummy
  slow = dummy.next

  while slow
    sum += slow.val
    hash[sum] = slow
    slow = slow.next
  end

  sum = 0
  fast = dummy
  while fast
    sum += fast.val
    if hash.has_key?(sum)
      fast.next = hash[sum].next
    end
    fast = fast.next
  end

  return dummy.next
end

Solution - PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function removeZeroSumSublists($head) {
  $map = [];
  $dummy = new ListNode(0);
  $sum = 0;
  $dummy->next = $head;
  $fast = $dummy;
  $slow = $head;

  while ($slow) {
      $sum += $slow->val;
      $map[$sum] = $slow;
      $slow = $slow->next;
  }

  $sum = 0;
  while ($fast) {
      $sum += $fast->val;
      if (isset($map[$sum])) {
      $fast->next = $map[$sum]->next;
      }
      $fast = $fast->next;
  }
  return $dummy->next;
}

LeetCode 傳送門 - Remove Zero Sum Consecutive Nodes from Linked List