阳泉市住房保障和城乡建设管理局网站,珠海微网站建设,中国网页设计欣赏,网页设计与制作课程建设规划方案题目描述
给你一个链表的头节点 head #xff0c;该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val 0 。
对于每两个相邻的 0 #xff0c;请你将它们之间的所有节点合并成一个节点#xff0c;其值是所有已合并节点的值之和。然后将所有 0 …题目描述
给你一个链表的头节点 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 * 10^5] 内0 Node.val 1000不 存在连续两个 Node.val 0 的节点链表的 开端 和 末尾 节点都满足 Node.val 0
思路
这是一道字符串模拟题我们需要模拟合并的过程。首先为链表添加一个虚拟头节点定义pre指针用来记录结果链表的最后一个节点初始是虚拟头节点定义cur指针来遍历链表。如果下一个节点的值不是0就将上一个节点的值加到下一个节点上。如果下一个节点的值是0就将本节点连接到结果链表上因为本节点的值已经是本段链表的值之和。最后再去除末尾的含0节点即可。
时间复杂度O(n)
空间复杂度O(1)
代码
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) {ListNode* dummmyHeadnew ListNode();ListNode* predummmyHead;ListNode* curhead-next;ListNode* tmp;while(cur-next!nullptr){// 下一个节点的值不是0让下一个节点的值加上当前节点的值if(cur-next-val!0){cur-next-valcur-val;}else{ // 下一个节点的值是0让pre-nextcur;prepre-next;}// 记录最后一个含0的节点的前一个节点if(cur-next-nextnullptr){tmpcur;}curcur-next;}// 还需要去除最后一个含0的节点tmp-nextnullptr;return dummmyHead-next;}
};
Python版
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def mergeNodes(self, head: Optional[ListNode]) - Optional[ListNode]:dummyHeadListNode()predummyHeadcurhead.nexttmpNonewhile cur.next!None:if cur.next.val!0:cur.next.valcur.valelse :pre.nextcurprepre.nextif cur.next.nextNone:tmpcurcurcur.nexttmp.nextNonereturn dummyHead.next
需要注意的地方
1.本题容易忽略最后一个节点也是含0节点需要删除最后一个节点。
