leetcode 2) Add Two Numbers

LV. Medium 🧐

https://leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode

 

문제

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.

 

문제 해결법

수가 뒤집혀서 저장되어 있고 리턴할 때도 뒤집어서 리턴해주기 때문에 0번째 인덱스부터 n번째 인덱스까지 차례대로 계산해주었다.

해당 자릿수에서 더한 값이 10이 넘어가면 flag를 true로 바꿔 다음 자릿수를 계산할 때 1를 더할 수 있게 해주었다.

 

해결 방법

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode *temp1 = l1;
		ListNode *temp2 = l2;
		bool flag = false;
		ListNode *start = NULL;
		ListNode *before = NULL;

		while (temp1 || temp2) {
			int num = 0;
			if (temp1) {
				num += temp1->val;
				temp1 = temp1->next;
			}
			if (temp2) {
				num += temp2->val;
				temp2 = temp2->next;
			}
			if (flag)
				num += 1;
			ListNode *node = new ListNode(num % 10);
			if (before == NULL)
				start = node;
			else
				before->next = node;
			before = node;
			flag = num / 10;
		}
		if (flag) {
			ListNode *node = new ListNode(1);
			before->next = node;
		}
		return start;
	}
};