[LeetCode] 2. Add Two Numbers

2. Add Two Numbers : https://leetcode.com/problems/add-two-numbers/ 

 

음이 아닌 Interger 수를 표현한 두 개의 링크드 리스트가 있다. 각 문자는 역순으로 저장되어 있고, 각 노드는 한개의 숫자를 담고 있다. 두 숫자를 합한 링크드 리스트를 반환하라. 

 

두 개의 숫자는 0을 제외하면, 0으로 시작하지 않는다. 

 

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:

• 링크드 리스트는 1에서 100개 사이의 노드를 가진다. 
• 0 <= Node.val <= 9
• 숫자는 0으로 시작하지 않는다. 

---

내가 푼 방법. 

 

- 입력이 숫자의 역순으로 주어졌기 때문에, 1의 자리부터 순차적으로 계산하는 것이 가장 효율 적이라 생각했습니다.   

/**
 * 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; }
 * }
 */

- 주석으로 주어진 자료형(ListNode)을 이용하여, 문제를 풀어야 했고, 리스트를 순회하고 결과를 출력할 때, 단방향 링크드 리스트이므로 시작 노드를 알고 있어야 출력을 할 수 있습니다. 또한 이전 노드를 알고 있어야 현재 계산된 노드로 링크를 걸 수 있습니다. 

- 자릿수 올림을 계산하여야 합니다. 

 

	/**
	* 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 c1 = null;
	ListNode c2 = null;
	ListNode s = null;
	ListNode p = null;
	ListNode n = null;
	int overflow = 0;
	c1 = l1;
	c2 = l2;
	while(c1 != null || c2 != null){
	int sum =0;
	if( c1 == null ){
	sum = c2.val + overflow;
	}else if( c2 == null){
	sum = c1.val + overflow;
	}else{
	sum = c1.val + c2.val + overflow;
	}
	if( sum > 9 ){
	n = new ListNode(sum-10);
	overflow = 1;
	}else{
	n = new ListNode(sum);
	overflow = 0;
	}
	if( p != null ){
	p.next = n;
	}
	p = n;
	if( s == null ){
	s = p;
	}
	c1 = (c1 == null || c1.next == null)? null: c1.next;
	c2 = (c2 == null || c2.next == null)? null: c2.next;;
	}
	if(overflow > 0){
	n = new ListNode(1);
	p.next = n;
	}
	return s;
	}
	}

view raw add_two_numbers.java hosted with ❤ by GitHub