“This is the 41st day of my participation in the First Challenge 2022.

preface

This is the second question in the Weekly Contest 281. On Medium, it examines the basic operation of linked lists. The difficulty is not very difficult.

describe

You are given the head of a linked list, which contains a series of integers separated by 0’s. The beginning and end of the linked list will have Node.val == 0.

For every two consecutive 0’s, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0’s.

Return the head of the modified linked list.

Example 1:

Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation: 
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 3 + 1 = 4.
- The sum of the nodes marked in red: 4 + 5 + 2 = 11.
Copy the code

Note:

The number of nodes in the list is in the range [3, 2 * 10^5].
0 <= Node.val <= 1000
There are no two consecutive nodes with Node.val == 0.
The beginning and end of the linked list have Node.val == 0.
Copy the code

parsing

According to the instructions, you get a head of a linked list containing a series of integers separated by 0. Node.val == 0 at the beginning and end of the list. For every two consecutive zeros, all nodes between them are merged into a single node whose value is the sum of all the merged nodes. The modified linked list should not contain any nodes with a value of 0. Returns the head of the modified list.

I used a more opportunistic method for this problem in the competition. It must be the basic operation of the linked list, but I directly traversed all the nodes of the linked list, stored all the values in a list L, and then through the operation of list L, Add the sum between the two zeros and initialize it as a node to the new list result.

The time complexity is O(N), and the space complexity is O(N). From the point of view of time, it can pass, a lot of time is spent in the initialization of the new node operation, almost pass.

answer

class Solution(object): def mergeNodes(self, head): """ :type head: Optional[ListNode] :rtype: Optional[ListNode] """ L = [] while head: L.append(head.val) head = head.next result = dummy = ListNode(-1) total = 0 for c in L: if c == 0: if total! =0: dummy.next = ListNode(total) dummy = dummy.next total = 0 total += c return result.nextCopy the code

The results

39/39 Test cases passed. Status: Accepted Runtime: 6346 MS Memory Usage: 201.7 MBCopy the code

parsing

As far as I’m concerned, there is no technical content in this mindless solution, although it is possible to cut corners and save time in order to gain time. We should use linked list operations, not borrow lists to complete problems.

Actually thought is also very simple, because the first node is 0, so we use pointer cur starting from the second node traverse the entire list of node value, we also initialize a false pointer dummy, we will use it the ith a nonzero interval and placed on the list of the ith node position, so after traversal in the end, We simply assign dummy.next to None and return head, where each value is the sum of each non-zero interval.

The time complexity is still O(N), but the space complexity is O(1), because no extra space is used, just changes made on the original list.

answer

class Solution(object): def mergeNodes(self, head): """ :type head: Optional[ListNode] :rtype: Optional[ListNode] """ cur = head.next dummy = head while cur: if cur.val! =0: dummy.val += cur.val cur = cur.next else: if not cur.next: dummy.next = None break dummy = dummy.next dummy.val = 0 cur = cur.next return headCopy the code

The results

39 / 39 test cases passed.
Status: Accepted
Runtime: 4258 ms
Memory Usage: 132 MB
Copy the code

The original link

Leetcode.com/contest/wee…

Your support is my biggest motivation