[LeetCode] 2.Add Two Numbers

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

Add Two Numbers - LeetCode

1. Problem

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.

2.Code

package leetCode;

import java.util.ArrayList;

public class AddTwoNumbers {
	public static void main(String[] args) {
		ListNode resultNode = new ListNode();
		//[2,4,3]
		ListNode node1 = new ListNode(3);
		ListNode node2 = new ListNode(4, node1);
		ListNode node3 = new ListNode(2, node2);

		//[5,6,4]
		ListNode nodeA = new ListNode(4);
		ListNode nodeB = new ListNode(6, nodeA);
		ListNode nodeC = new ListNode(5, nodeB); 

		resultNode = addTwoNumbers(node3, nodeC);
/*
 * 확인용
 * 		while(resultNode != null) {
			System.out.println(resultNode.val); 
			resultNode = resultNode.next;
		}
*/
	}
	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //ArrayList 생성
        ArrayList<Integer> arrList1 = makeArrList(l1);
        ArrayList<Integer> arrList2 = makeArrList(l2);
        
        //ArrayList 더함
        ArrayList<Integer> sumResult = new ArrayList<>();
        if(arrList1.size() >= arrList2.size()) {
            sumResult = sumArrList(arrList1, arrList2);
        } else { 
            sumResult = sumArrList(arrList2, arrList1);   
        }
        
        // List를 ListNode로 변환
        ListNode result = listToNode(sumResult);
        return result;   
    }
    
    //ListNode를 ArrayList로 변환하는 메소드
    public static ArrayList<Integer> makeArrList(ListNode ln) {
        ArrayList<Integer> arrList = new ArrayList<>();
        while(ln != null) {
            arrList.add(ln.val);
            ln = ln.next;
        }
        return arrList;
    }
    
    //두개의 ArrayList를 더한 ArrayList를 반환하는 메소드
    public static ArrayList<Integer> sumArrList(ArrayList<Integer> longList, ArrayList<Integer> shortList) {
        ArrayList<Integer> sumResult = new ArrayList<>();
        int temp = 0;
        int sum = 0;
        
        //짧은List값까지 짧은List + 긴List;
        for(int i = 0; i < shortList.size(); i++) {
                sum = temp + longList.get(i) + shortList.get(i);
                if(sum >=10) {
                    sumResult.add(sum - 10);
                    temp = 1;
                } else {
                    sumResult.add(sum);
                    temp = 0;
            }
        }
        
        //짧은List이후 값부터는 LongList + temp;
        for(int i = shortList.size(); i < longList.size(); i++) {
            sum = temp + longList.get(i);
            if(sum >=10) {
                    sumResult.add(sum - 10);
                    temp = 1;
                } else {
                    sumResult.add(sum);
                    temp = 0;
                }
        }
        
        //마지막 값 더해서 10넘으면 자리올림수~
        if(temp == 1) {
        	sumResult.add(temp);
        }
        return sumResult;
    }
    
    public static ListNode listToNode(ArrayList<Integer> al) {
    	ListNode result = new ListNode();
    	ListNode head = new ListNode();
    	
    	for(int i = 0; i < al.size(); i++) {
    		if(i==0) {
    			result.val = al.get(i);
    			head = result;
    		} else {
    			ListNode n = new ListNode(al.get(i));
    			head.next = n;
    			head = n;
    		}
    	}
    	return result;
    }
}

 

3.Report

처음에는 굳이 ArrayList에 있는 숫자들을 각 자리수로 더해 int형으로 받아서 그걸 또 뒤집고 더하려고 했다....(오류천지)

그냥 두 개의 ArrayList를 더하고 그대로 NodeList로 변환하면 됐다.

 

4.Learned

-ArrayList 사용법

 

5.Improvements

두 개의 NodeList를 바로 더해서 출력할 수 있다