[LeetCode] 2181. Merge Nodes in Between Zeros

https://leetcode.com/problems/merge-nodes-in-between-zeros/description/

leetcode - Merge Nodes in Between Zeros

문제 유형 : 연결리스트, 투 포인터

문제 난이도 : Medium

 

문제

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.

 

연결리스트의 head가 주어진다. 

값이 0으로 구분되는 일련의 숫자 노드들로 구성되어있다.

시작과 끝의 값도 0으로 되어있다.

 

각 0들에 대해서, 노드들의 값들을 모두 합쳐서 한 노드로 만들어라. 변형된 리스트는 0이 없어야 한다.

변형된 연결리스트의 head를 반환하라.

 

풀이

in-place로 풀이가 가능하다.

투포인터를 통해서 0다음의 노드, 다음 0이전의 노드까지 모두 값을 합치고, 중간의 노드들을 없앤다.

아래 예시에서, left = 3, right = 두 번째 0을 가리킨다 하면,

임시 변수와 노드를 가리키는 포인터를 만들어서 left부터 right이전까지 가는 것이다.

임시 포인터로 left부터 right까지 이동하면서 값을 누적하는데, next도 지운다.

그리고 left의 next를 right으로 한다.

 

right를 1회 다음으로 이동한다.

이를 끝까지 계속 반복한다.

 

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

/**
 * 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) {
        auto left = head;
        auto right = head -> next;

        while(right != NULL) {
            if(right -> val == 0) {
                left = left -> next;
                int val = 0;
                auto node = left;
                while(node != right) {
                    val += node -> val;
                    auto prev = node;
                    node = node -> next;
                    prev -> next = NULL;
                }
                left -> val = val;
                left -> next = right;
            }
            right = right -> next;
        }
        left -> next = NULL;
        return head -> next;
    }
};