[LeetCode] 1171. Remove Zero Sum Consecutive Nodes from Linked List

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/description/

Leetcode - Remove Zero Sum Consecutive Nodes from Linked List

문제 유형 : 연결리스트, 재귀

문제 난이도 : Medium

 

문제

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list.  You may return any such answer.

 

(Note that in the examples below, all sequences are serializations of ListNode objects.)

 

연결리스트의 head가 주어진다. 이 연결리스트에서 합이 0인 부분 연결리스트를 제거해야 한다.

 

풀이

투 포인터를 이용할 수도 있겠지만, 재귀를 이용하면 훨씬 효율적이다.

현재 노드부터 순차적으로 순회하면서, sum을 구한다.

만약 sum이 0이 된다면, 부분 연결리스트를 없애고(head에서 그 자리로 포인터 변경),

그 부분부터 다시 시작한다.

 

만약 순회하는 내내 없다면, 현재 노드의 다음 노드를 호출하여 재귀호출한다.

head를 반환한다.

 

코드

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* removeZeroSumSublists(ListNode* head) {
        if (head == NULL) return head;

        auto curr = head;
        int sum = 0;

        while(curr != NULL) {
            sum += curr -> val;
            if(sum == 0) {
                head = curr -> next;
                return removeZeroSumSublists(head);
            }

            curr = curr -> next;
        }

        head -> next = removeZeroSumSublists(head -> next);
        return head;
    }
};