LeetCode 题解工作台
合并零之间的节点
给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。 对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。 返回修…
2
题型
7
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们定义一个虚拟头节点 ，以及一个指向当前节点的指针 ，一个变量 用来记录当前节点的值之和。 接下来，我们从链表的第二个节点开始遍历，如果当前节点的值不为 0，我们将其加到 上，否则我们将 加到 的后面，并将 置为 0，更新 为 的下一个节点。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。
对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。
返回修改后链表的头节点 head 。
示例 1：
输入：head = [0,3,1,0,4,5,2,0] 输出：[4,11] 解释： 上图表示输入的链表。修改后的链表包含： - 标记为绿色的节点之和：3 + 1 = 4 - 标记为红色的节点之和：4 + 5 + 2 = 11
示例 2：
输入：head = [0,1,0,3,0,2,2,0] 输出：[1,3,4] 解释： 上图表示输入的链表。修改后的链表包含： - 标记为绿色的节点之和：1 = 1 - 标记为红色的节点之和：3 = 3 - 标记为黄色的节点之和：2 + 2 = 4
提示：
- 列表中的节点数目在范围
[3, 2 * 105]内 0 <= Node.val <= 1000- 不 存在连续两个
Node.val == 0的节点 - 链表的 开端 和 末尾 节点都满足
Node.val == 0
解题思路
方法一：模拟
我们定义一个虚拟头节点 ，以及一个指向当前节点的指针 ，一个变量 用来记录当前节点的值之和。
接下来，我们从链表的第二个节点开始遍历，如果当前节点的值不为 0，我们将其加到 上，否则我们将 加到 的后面，并将 置为 0，更新 为 的下一个节点。
最后，我们返回 的下一个节点。
时间复杂度 ，空间复杂度 。其中 为链表的长度。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = tail = ListNode()
s = 0
cur = head.next
while cur:
if cur.val:
s += cur.val
else:
tail.next = ListNode(s)
tail = tail.next
s = 0
cur = cur.next
return dummy.next
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Ability to manipulate linked list pointers correctly.
- question_mark
Skill in optimizing space complexity by modifying the list in-place.
- question_mark
Demonstrating an understanding of traversal techniques to achieve linear time complexity.
常见陷阱
外企场景- error
Failing to correctly update the linked list pointers, leading to incorrect results.
- error
Overcomplicating the problem by creating unnecessary data structures.
- error
Not handling edge cases such as when there are multiple zeros or when the list is very large.
进阶变体
外企场景- arrow_right_alt
Handling lists with multiple consecutive zeros and ensuring correct merging.
- arrow_right_alt
Modifying the problem to work with circular linked lists.
- arrow_right_alt
Expanding the problem to allow for additional operations, such as multiplying the sums instead of adding them.