[7. 연결리스트] 7.13 리스트로 표현된 정수의 덧셈

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

https://msugi.tistory.com/47

[7. 연결리스트] 7.0 연결리스트 기초 작업

연결리스트 문제를 풀기전 LinkedList를 위와 같이 직접 구현했다. 위 LikedList를 이용하여 문제를 풀 예정이다.

---

Q 7.13 리스트로 표현된 정수의 덧셈

각 노드에 숫자가 쓰인 연결리스트를 하나의 정수로 생각하며 한자리 라고 할때(0~9) 두 리스트를 더하여 합을 출력하는 리스트를 작성하라.
ex) L1-> 4 -> 1 -> 3          L2->9->0->7          =   L->1->3->2->0

---

해당문제의 문제점은 덧셈을 할때 일의 자리부터 더해야한다는점과 올림이 일어나 추가 공간을 생산해야 한다는 점이 있다.
표기를 413 일때 4가 Head 3이 Tail이라고 할때 tail부터 더하여 나온 결과를 뒤집는 방법을 사용했다.

해당내용의 소스코드와 결과는 다음과 같다.

// 7.13 리스트로 표현된 정수의 덧셈#include "LinkedList.h"
 
//각 리스트의 정수는 10을 넘지 못한다. 0~9 사이의 숫자임
List<int>* AddTwoNumbers(List<int>* L1, List<int>* L2)
{
    LinkedList<int> L;
    Node<int>* TempList;
    Node<int>* L1Tail = L1->TailNode;
    Node<int>* L2Tail = L2->TailNode;
    if (!L1Tail || !L2Tail) { return nullptr; }
 
    
    int AddListData = L1Tail->data + L2Tail->data;
    L.AddNode(L.list, L.CreateNode(AddListData));
    int count = 1;
    Node<int>* ListHead = L.list->HeadNode;
 
    L1Tail = L1Tail->PrevNode;
    L2Tail = L2Tail->PrevNode;
 
    while (!(L1Tail == nullptr && L2Tail == nullptr))
    {
        if (L1Tail == nullptr || L2Tail == nullptr)
        {
            AddListData = (L1Tail == nullptr) ? L2Tail->data : L1Tail->data;
            L1Tail == nullptr ? L2Tail = L2Tail->PrevNode : L1Tail = L1Tail->PrevNode;
        }
        else
        {
            AddListData = L1Tail->data + L2Tail->data;
            L1Tail = L1Tail->PrevNode;
            L2Tail = L2Tail->PrevNode;
        }
        L.AddNode(L.list,L.CreateNode(AddListData));
        count++;
        
        if (ListHead->data >= 10)
        {
            ListHead->NextNode->data += ListHead->data / 10;
            ListHead->data = ListHead->data % 10;
        }
        ListHead = ListHead->NextNode;
    }
 
    if (ListHead->data >= 10)
    {
        L.AddNode(L.list, L.CreateNode(ListHead->data / 10));
        ListHead->data = ListHead->data % 10;
        count++;
        ListHead = ListHead->NextNode;
    }
 
    L.list->HeadNode = ListHead;
    for (int i = 0; i < count; i++)
    {
        TempList = ListHead->PrevNode;
        ListHead->PrevNode = ListHead->NextNode;
        ListHead->NextNode = TempList;
 
        ListHead = ListHead->NextNode;
    }
    L.list->TailNode = ListHead->PrevNode;
 
    L.list->HeadNode->PrevNode = nullptr;
    if (L.list->TailNode->data == 0)
    {
        L.list->TailNode = nullptr;
    }
    else
    {
        L.list->TailNode->NextNode = nullptr;
    }
    L.list->Count = count;
 
    return L.list;
}

L10과 L11은 올림을 확인할수있는 54321 값을 사용하여 더하였다.
54321 + 54321 = 108642 가 나오면된다.

for (int i = 5; i > 0; i--)
{
    L10.AddNode(L10.list, L10.CreateNode(i));
    L11.AddNode(L11.list, L11.CreateNode(i));
}
L10.list->TailNode->NextNode = nullptr;
L10.list->HeadNode->PrevNode = nullptr;
L11.list->TailNode->NextNode = nullptr;
L11.list->HeadNode->PrevNode = nullptr;
 
L12.list = AddTwoNumbers(L10.list,L11.list);
std::cout << "\n7-13) " << std::endl;
L12.PrintAllNode(L12.list); //7-13

결과