2181 Merge Nodes in Between Zeros

2181. Merge Nodes in Between Zeros / c++ / Medium / 13분

문제 및 코드

문제 링크

class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        ListNode* current = head->next;
        delete head;
        head = current;

        while (current != nullptr)
        {
            ListNode* next = current->next;
            while (next->val != 0)
            {
                current->val += next->val;
                current->next = next->next;
                delete next;
                next = current->next;
            }

            if (next->next == nullptr)
            {
                current->next = nullptr;
                delete next;
                break;
            }
            else
            {
                current->next = next->next;
                delete next;
                current = current->next;
            }
        }

        return head;
    }
};

접근 방식

자료 구조 / 링크드 리스트

1. 링크드 리스트에서 0이 아닌 값들을 합쳐서 반환하는 문제였다.
   (ex. 0 1 2 3 0 4 5 0 이라면, 6(1+2+3) 9(4+5) 를 반환)
2. 단순 값만 더하는 건 엄청 쉬웠지만, 링크드 리스트 구조를 유지하면서, 노드의 삭제가 필요해서 생각을 요구했다.
3. 내가 적용한 방식은, 0이 아닌 첫 번째 원소에다 이후의 값들을 더해주는 것이었다.
   1. 0 1 2 3 0 4 5 0
   2. 0 3 3 0 4 5 0 (1 + 2)
   3. 0 6 0 4 5 0 (3 + 3)
   4. 0 6 0 9 0
4. 다음으로 해야할 것은, 0인 값들은 링크드 리스트에서 제거해야 했다.
5. 제일 처음 0은 시작할 때 제거
6. 그 다음부터 나오는 0에 대해선
   1. 만약 0 다음에 노드가 또 있다면 (끝이 아님) : 0 전 후의 노드를 연결하고 0 노드를 삭제
   2. 만약 0 다음에 노드가 없다면 (끝) : 현재 노드의 next를 nullptr로 하고 0 노드를 삭제
7. 해결

생각해 볼 점

1. 자료 구조를 공부할 때 가장 처음 나오는 자료 구조인 링크드 리스트를 되짚어 볼 수 있는 문제였다.
2. 지금 생각해보니 0인 노드를 삭제하지 말고 3번 로직을 0인 노드에서 실행했으면 더 효율적이었을 것 같다. (0 1 2 3 을 더하고 다음 0 4 5 를 더하고 마지막 0은 탈락)