[리트코드 / LeetCode] 2. Add Two Numbers 풀이 - C++

문제 원문

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0] Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

코드 원문

/**
 * 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 {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
    }
};

풀이

주어진 ListNode 구조체로 덧셈을 구현하는 문제입니다.

구조체가 주어진 문제를 자주 접해보지 않아 초반엔 조금 얼타서 매개변수 컨트롤도 잘못하고 뻘짓하게 되었네요..

아무튼 이 문제는 Linked List를 컨트롤하는 것이 중요합니다.

저는 두 리스트의 값을 더하여 결과 리스트에 넣으면서 문제를 해결했습니다.

그러는 과정에 올림수 처리가 필요하여 작업해주었습니다.

성공 코드

/**
 * 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 {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
	ListNode* l2 = new ListNode(5, new ListNode(6, new ListNode(4)));

	int num1 = 0;
	int num2 = 0;
	ListNode *answer = new ListNode();
	ListNode *temp1, *temp2, *AnswerTemp;
	temp1 = l1;
	temp2 = l2;
	AnswerTemp = answer;
	int count = 0;

	bool bVal1, bVal2;
	bVal1 = true;
	bVal2 = true;

	bool UpPoint = false;
	int sum;

	while (true)
	{
		//초기화
		sum = 0;
		num1 = 0;
		num2 = 0;
		//List 1
		if (bVal1)
		{
			num1 = temp1->val;
			temp1 = temp1->next;
			if (temp1 == NULL)
				bVal1 = false;
		}
		//List 2
		if (bVal2)
		{
			num2 = temp2->val;
			temp2 = temp2->next;
			if (temp2 == NULL)
				bVal2 = false;
		}
		//합 계산
		sum = num1 + num2;
		//올림수 덧셈
		if (UpPoint)
		{
			sum += 1;
			UpPoint = false;
		}
		//합한 값이 10 이상일때 올림수를 설정
		if (sum >= 10)
		{
			printf("%d : UpPoint\n", sum);
			sum -= 10;
			UpPoint = true;
		}

		//값 설정
		AnswerTemp->val = sum;

		if (!bVal1 && !bVal2)
		{
			//두 수가 마지막 노드 일때 올림수가 있으면 처리
			if (UpPoint)
			{
				AnswerTemp->next = new ListNode(1);
			}
			break;
		}

		//노드 추가
		AnswerTemp->next = new ListNode();
		AnswerTemp = AnswerTemp->next;

		++count;
	}
        
        return answer;
    }
};

결과

Runtime: 52 ms, faster than 11.77% of C++ online submissions for Add Two Numbers.

Memory Usage: 71.6 MB, less than 42.53% of C++ online submissions for Add Two Numbers.