2181. Merge Nodes in Between Zeros

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        ListNode *ret = new ListNode(-1), *ans = ret;
        // spilt lists
        ListNode *cur = head->next;
        int sum = 0;
        while(cur){
            if(cur->val!=0){
                sum+=cur->val;
            }
            else if(cur->val == 0){
                ret->next = new ListNode(sum);
                ret = ret->next;
                sum = 0;
            }
            cur=cur->next;
            
        }
        return ans->next;
    }
};
  • other version
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
/**
 * 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 *ret = new ListNode(-1), *ans = ret;
        // spilt lists
        ListNode *cur = head->next;
        int sum = 0;
        while(cur){
            while(cur && cur->val !=0){
                sum+=cur->val;
                cur=cur->next;
            }
            ret->next = new ListNode(sum);
            ret= ret->next;
            sum = 0;
            cur = cur->next;
        }
        return ans->next;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)