[Leetcode] 2816.

문제 링크 : https://leetcode.com/problems/double-a-number-represented-as-a-linked-list/?envType=daily-question&envId=2024-05-07

🖥️ 시작하며

간단한 연결 리스트 문제다.

받은 연결리스트에서 숫자를 문자열로 하나하나 저장
문자열을 숫자로 바꾼 후, 2배
결과물을 다시 연결 리스트로 저장

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        # 숫자를 문자열로 먼저 변환
        text = ""
        cur = head
        while cur:
            text += str(cur.val)
            cur = cur.next

        # 문자열을 숫자로 변환한 다음 2를 곱함
        doubled_num = int(text) * 2

        # 곱한 결과를 다시 연결 리스트로 변환
        # 결과 숫자를 문자열로 변환한 다음 각 자릿수를 연결 리스트 노드로
        dummy_head = ListNode()
        cur = dummy_head
        for char in str(doubled_num):
            cur.next = ListNode(int(char))
            cur = cur.next

        return dummy_head.next

..라고 하면, 메모리 초과가 발생한다!

테스트케이스에서 연결 리스트가 굉장히 긴 케이스가 존재하기 때문에, 이렇게 2를 곱하는 방식으로는 오버플로우가 일어나 오류가 생긴다.

그렇다면, 우선 리스트의 순서를 뒤집은 후 Carry 를 이용해 곱하기의 결과를 전달해 업데이트하는 방식을 사용해야 한다.

⚙️ Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        cur = head
        while cur:
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        return prev

    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        # 연결리스트 뒤집기
        head = self.reverseList(head)
        cur = head
        carry = 0

        # 각 노드의 값을 두 배로 만듭니다.
        while cur:
            doubled_value = cur.val * 2 + carry
            cur.val = doubled_value % 10
            carry = doubled_value // 10
            # carry가 남아 있는데 노드가 끝이면 하나 추가
            if not cur.next and carry:
                cur.next = ListNode(carry)
                break
            cur = cur.next

        # 다시 뒤집기
        return self.reverseList(head)

⚙️ C++

class Solution {
public:
    // 리스트 뒤집기 함수
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr;
        ListNode *cur = head;
        while (cur != nullptr) {
            ListNode *next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    // 리스트 두 배로 만들기 함수
    ListNode* doubleIt(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }

        // 리스트 뒤집기
        head = reverseList(head);
        ListNode *cur = head;
        int carry = 0;

        // 노드를 순회하면서 값을 두 배로 만들기
        while (cur != nullptr) {
            int doubled_value = cur->val * 2 + carry;
            cur->val = doubled_value % 10;
            carry = doubled_value / 10;

            // 마지막 노드이고 캐리가 남아있다면 새 노드 추가
            if (cur->next == nullptr && carry) {
                cur->next = new ListNode(carry);
                break;
            }
            cur = cur->next;
        }

        // 다시 리스트를 뒤집어 원래 순서로 복구
        return reverseList(head);
    }
};