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 contain a single digit. Add the two numbers and return it as a linked list.

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

두개의 Null값이 아닌 정수의 값을 담고있는 linked List를 input값으로 주어진다.이 숫자들은 거꾸로 저장되어있으며 각 노드마다 한 개의 정수를 포함하고 있다. 두 개의 숫자를 더한 값을 Linked List를 반환하라.

이 두 숫자는 결과가 0을 유도하거나, 혹은 숫자 자체가 0이 되지 않는 점을 참고하여라.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807

풀이 : 

내 풀이법

사람이 덧셈을 푸는 방식과 동일하게 생각하여 구현하였다.

총 케이스는 세가지가 있다.

1) 덧셈시 l1와 l2의 각 노드가 존재할때

2) l1가 l2보다 자리수가 적을때

3) l2가 l1보다 자리수가 적을때

위와 같은 조건에서 while문을 돌려서 두 linked list의 값을 더해주었다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode rst = result;
        int tmp = 0;
        int tmp_rst = 0;
        while((l1 != null) && (l2 != null)){
            rst.next = new ListNode();
            rst = rst.next;
            tmp_rst = 0;
            tmp_rst = l1.val + l2.val + tmp;
            tmp = tmp_rst / 10;
            rst.val = tmp_rst % 10;
            l1 = l1.next;
            l2 = l2.next;  
        }
        while(l1 != null){
            rst.next = new ListNode();
            rst = rst.next;
            tmp_rst = 0;
            tmp_rst = l1.val+ tmp;
            tmp = tmp_rst / 10;
            rst.val = tmp_rst % 10;
            l1 = l1.next; 
        }
        while(l2 != null){
            rst.next = new ListNode();
            rst = rst.next;
            tmp_rst = 0;
            tmp_rst = l2.val+ tmp;
            tmp = tmp_rst / 10;
            rst.val = tmp_rst % 10;
            l2 = l2.next; 
        }
        if(tmp != 0){
             rst.next = new ListNode();
            rst = rst.next;
            rst.val = tmp;
        }
        return result.next;
    }
    
}

메모리 사용량은 전체의 91.22%를 앞섰고, 런타임은 submit한 인원 중 71.67%을 앞섰다. 

 

참고 풀이법

 

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        
        return addRecursively(l1, l2, 0);
    }
    
    public ListNode addRecursively(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null && carry == 0) return null;         

        int v1 = l1 != null ? l1.val : 0;
        int v2 = l2 != null ? l2.val : 0;

        int sum = v1 + v2 + carry;
        carry = sum / 10;
        ListNode temp = new ListNode(sum % 10);

        temp.next = addRecursively(l1 != null ? l1.next : null, l2 != null ? l2.next : null, carry);
        
        return temp;
    }
}

이 코드는 재귀함수를 이용하여 코드를 보다 간결하게 작성하였다.

자리수가 올라가야 할 때마다 똑같은 작업을 하기 때문에, while로 사용하는것도 한가지 방법이지만 재귀로 사용하는 것이 더 깔끔한 느낌이 있다.

 

이 코드는 런타임은 전체 100%를 앞질렀고, 메모리 사용량은 99,79%를 앞질렀다.

시간복잡도 : O(Max(m,n))

공간복잡도 : O(Max(m,n))