2181. 合并零之间的节点：
给你一个链表的头节点 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
分析
- 面对这道算法题目，二当家的陷入了沉思。
- 直接新建一条链表相对简单一点。
- 事实上可以原地修改。
- 一个值得注意的点：c和c++需要手动管理内存，所以理论上需要将中间被合并的那些节点的内存手动释放掉。
题解
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeNodes(ListNode head) {
ListNode cur = head;
while (cur != null) {
if (cur.next.val != 0) {
// 合并
cur.val += cur.next.val;
cur.next = cur.next.next;
} else {
// 跳到下一个区间
cur.next = cur.next.next;
cur = cur.next;
}
}
return head;
}
}c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeNodes(struct ListNode* head){
struct ListNode* cur = head;
while (cur) {
if (cur->next->val) {
// 合并
cur->val += cur->next->val;
cur->next = cur->next->next;
} else {
// 跳到下一个区间
cur->next = cur->next->next;
cur = cur->next;
}
}
return head;
}c++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeNodes(ListNode* head) {
struct ListNode* cur = head;
while (cur) {
if (cur->next->val) {
// 合并
cur->val += cur->next->val;
cur->next = cur->next->next;
} else {
// 跳到下一个区间
cur->next = cur->next->next;
cur = cur->next;
}
}
return head;
}
};python
# 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]:
cur = head
while cur:
if cur.next.val:
# 合并
cur.val += cur.next.val
cur.next = cur.next.next
else:
# 跳到下一个区间
cur.next = cur.next.next
cur = cur.next
return head
go
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeNodes(head *ListNode) *ListNode {
cur := head
for cur != nil {
if cur.Next.Val != 0 {
// 合并
cur.Val += cur.Next.Val
cur.Next = cur.Next.Next
} else {
// 跳到下一个区间
cur.Next = cur.Next.Next
cur = cur.Next
}
}
return head
}rust
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn merge_nodes(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut cur = &mut head;
while cur.is_some() {
if (cur.as_ref().unwrap().next.as_ref().unwrap().val != 0) {
// 合并
cur.as_mut().unwrap().val += cur.as_ref().unwrap().next.as_ref().unwrap().val;
cur.as_mut().unwrap().next = cur.as_mut().unwrap().next.as_mut().unwrap().next.take();
} else {
// 跳到下一个区间
cur.as_mut().unwrap().next = cur.as_mut().unwrap().next.as_mut().unwrap().next.take();
cur = &mut cur.as_mut().unwrap().next;
}
}
return head;
}
}原题传送门：https://leetcode-cn.com/problems/merge-nodes-in-between-zeros/
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
