2. Add Two Numbers

문제

• 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.
  

  

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

  Example 2:Example 3:
  
  • 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.
• Constraints:
• Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]
• Input: l1 = [0], l2 = [0] Output: [0]
• Example 1:
• You may assume the two numbers do not contain any leading zero, except the number 0 itself.

 

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

Add Two Numbers - LeetCode

 

 

풀이

return용 노드 생성 후 해당 노드를 복사하여 사용했다.

l1노드나 l2노드를 끝까지 돌면서 더한 값의 나머지를 복사용 노드의 next에 넣고, 현재 가리키는 노드를 다음으로 이동해가며 반복했다.

while문이 끝나고 덧셈의 마지막 carry가 있는 경우 한번 더 복사용 노드에 넣고, return 시 return용 노드의 다음을 return하도록 했다. (응답용 노드의 다음부터 더한 값의 나머지를 넣었기 때문)

 

 

코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {    
		ListNode res = new ListNode(0);
		ListNode tmp = res;
		int carry = 0;
		
		while(l1 != null || l2 != null) {
			int add = (l1 != null? l1.val : 0) + (l2 != null? l2.val : 0) + carry;
			carry = add / 10;
			add = add % 10;
			tmp.next = new ListNode(add);
			tmp = tmp.next;
			if(l1 != null)l1 = l1.next;
			if(l2 != null)l2 = l2.next;
		}
		
		if(carry != 0) {
			tmp.next = new ListNode(carry);
		}
		
		res = res.next;

		return res;
	}
}

 

 

결과

Runtime: 3 ms

Memory Usage: 45 MB