#include <bits/stdc++.h>
/****************************************************************

Following is the class structure of the Node class:

class Node
{
public:
int data;
Node *next;
Node(int data)
{
this->data = data;
this->next = NULL;
}
};

*****************************************************************/

Node* addFirstAndReversedSecondHalf(Node* head)
{
//base case
if (!head)
{
return NULL;
}
else if (!head->next)
{
return head;
}

//mark middle
Node* slow = head;
Node* fast = head;
Node* mark = NULL;
int countN = 0;
bool more = false;
while (fast&&fast->next)
{
slow = slow -> next;
fast = fast -> next -> next;
countN++;
}
if (!fast)
{
mark = slow;
countN++;
}
else
{
mark = slow -> next;
more = true;
countN +=2;
}

//fill the vector
std::vector<std::vector<int>> num(3,std::vector<int>(countN, 0));
slow = head;
for(int i = 1; i < countN; i++)
{
num[0][i] = slow->data;
slow = slow -> next;
}
for (int i = countN-1; slow != NULL; i--)
{
num[1][i] = slow->data;
slow = slow -> next;
}
//add two nums
int increment = 0;
for (int i = countN-1; i >= 0; i--)
{
num[2][i] = (num[0][i]+num[1][i]+increment)%10;
increment = (num[0][i]+num[1][i])/10;
}

//check when the num begins
int begin = 0;
while (num[2][begin] == 0)
{
if (begin >= countN)
{
Node* result = new Node(0);
return result;
}
begin++;
}

//fill the linked list
Node* result = new Node(num[2][begin]);
begin++;
Node* resultPointer = result;
while (begin < countN)
{
resultPointer -> next = new Node(num[2][begin]);
resultPointer = resultPointer -> next;
begin++;
}
return result;

}






노드 길이가 개 커지면 에러남 왜지