addTwoHugeNumbers

두 개의 큰 정수가 링크드 리스트로 주어졌습니다. 각 링크드 리스트 요소는 0부터 9999까지의 숫자로, 정확히 4자리 숫자를 나타냅니다. 나타낸 숫자에는 선행 0이 있을 수 있습니다. 이 두 큰 정수를 더하고 결과를 동일한 형식으로 반환하는 것이 문제입니다.

예시:

a = [9876, 5432, 1999]이고 b = [1, 8001]인 경우, 결과는 [9876, 5434, 0]이 됩니다. 설명: 987654321999 + 18001 = 987654340000.
a = [123, 4, 5]이고 b = [100, 100, 100]인 경우, 결과는 [223, 104, 105]가 됩니다. 설명: 12300040005 + 10001000100 = 22301040105.

// Singly-linked lists are already defined with this interface:
// class ListNode<T> {
//   public T value { get; set; }
//   public ListNode<T> next { get; set; }
// }

ListNode<int> solution(ListNode<int> a, ListNode<int> b) {
    
    a = ReverseLinkedList(a);
    b = ReverseLinkedList(b);
    ListNode<int> dummyHead = new ListNode<int>();
    dummyHead.value = 0;
    ListNode<int> current = dummyHead;
    int carry = 0;
    
    while(a != null || b != null || carry != 0){
        int sum = carry;
        if(a != null){
            sum += a.value;
            a = a.next;
        }
        if(b != null){
            sum += b.value;
            b = b.next;
        }
        carry = sum / 10000;
        ListNode<int> newNode = new ListNode<int>();
        newNode.value= sum % 10000;
        current.next = newNode;
        current = current.next;
    }
    return ReverseLinkedList(dummyHead.next);
}
ListNode<int> ReverseLinkedList(ListNode<int> head)
    {
        ListNode<int> prev = null;
        ListNode<int> current = head;

        while (current != null)
        {
            ListNode<int> next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        return prev;
    }

먼저, 주어진 링크드 리스트를 역순으로 변환합니다. 이는 숫자를 더할 때 자릿수를 처리하기 위해 필요합니다.
dummyHead라는 가상의 노드를 생성합니다. 이 노드는 결과 링크드 리스트의 시작을 나타냅니다.
current 변수를 dummyHead로 초기화하고, carry 변수를 0으로 설정합니다.
a와 b의 각 자릿수를 더하고, 이전 자릿수에서의 carry 값을 더합니다.
만약 a나 b가 null이 아니면 해당 노드를 다음 노드로 이동합니다.
덧셈 결과를 10,000으로 나눈 몫을 carry로 설정하고, 나머지를 새로운 노드의 값으로 설정합니다.
current.next를 새로운 노드로 연결하고, current를 새로운 노드로 업데이트합니다.
반복하여 모든 자릿수를 더합니다.
최종 결과 링크드 리스트를 다시 역순으로 변환하여 반환합니다.