[LeetCode] 2816. Double a Number Represented as a Linked List

https://leetcode.com/problems/double-a-number-represented-as-a-linked-list/description/

leetcode - Double a Number Represented as a Linked List

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

문제 난이도 : Medium

 

문제

You are given the head of a non-empty linked list representing a non-negative integer without leading zeroes.

Return the head of the linked list after doubling it.

 

연결리스트의 Head를 받습니다.

이 연결리스트는 양의 정수를 의미합니다.

두 배 하시오.

 

풀이

재귀적으로 풀 수 있겠다.

만약 연결리스트의 tail까지 왔다면, tail의 값은 기존 값에 두 배를 하고 10을 나눈 나머지로 하면 된다.

10으로 나눈 값, 즉 캐리는 위 자리수에서 이용한다.

 

먼저 다음 노드를 재귀탐색한 후, 그 이전 노드에서의 값은 기존 값에 두 배를 하고 캐리를 더한 값에 10을 나눈 나머지로 하면 된다.

10으로 나눈 값, 즉 캐리는 위 자리수에서 이용할 것이다.

 

재귀를 통해 다시 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 {
private:
    int carry = 0;
public:
    void solve(ListNode* node) {
        if(node->next == nullptr) {
            int x = (node->val * 2) + carry;
            node->val = x % 10;
            carry = x / 10;
            return;
        }
        solve(node->next);
        int x = node->val * 2 + carry;
        carry = x / 10;
        node->val = x % 10;
    }
    ListNode* doubleIt(ListNode* head) {
        solve(head);
        if(carry > 0) {
            ListNode* newNode = new ListNode(carry);
            newNode->next = head;
            head = newNode;
        }
        return head;
    }
};