Linked List | Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

두 Linked List가 있는데, Singly Linked List이고, 더한 값을 Linked List로 리턴하라는 문제이다. 하지만 덧셈을 할 때, 제일 작은 수부터 계산을 하기 때문에, 그부분을 어떻게 접근할지 고민해야한다. 조건은 아래와 같다.

노드 숫자의 크기는 digit이기때문에 계산을 하는데는 문제가 없지만, 노드 갯수가 최대 100개까지 될 수 있기 때문에, integer이나 long으로 변환해서 계산을 하면 overflow가 날 위험이 있다. 그래서 첫번째로는 String으로 만들어서 각 캐릭터를 더해서 새로운 리스트에 넣는 방법을 생각했는데, 그것 말고도 만약 LinkedList를 뒤집을 수 있으면, O(N)으로, 그리고 따로 스트링을 쓰지 않고도 계산할 수 있다는 아이디어가 떠올라서 그렇게 접근했다. 조건에서 보여지듯, leading zeros가 없다는 조건도 있다. 풀이는 아래와 같다.

 

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode curr = null;
        int carry = 0;
        while(l1 != null || l2 != null){
            int val1 = l1 == null ? 0 : l1.val;
            int val2 = l2 == null ? 0 : l2.val;
            int sum = val1 + val2 + carry;
            ListNode newNode = new ListNode(sum % 10);
            newNode.next = curr;
            curr = newNode;
            carry = sum / 10;
            l1 = l1 == null ? l1 : l1.next;
            l2 = l2 == null ? l2 : l2.next;
        }
        if(carry != 0) {
            ListNode newNode = new ListNode(carry);
            newNode.next = curr;
            curr = newNode;
        }
        return curr;
    }
    
    private ListNode reverseList(ListNode node){
        ListNode prev = null;
        ListNode temp = null;
        while(node != null){
            temp = node.next;
            node.next = prev;
            prev = node;
            node = temp;
        }
        return prev;
    }
    
    private String printList(ListNode node){
        StringBuilder sb = new StringBuilder();
        while(node != null){
            sb.append(node.val + ", ");
            node = node.next;
        }
        return sb.toString();
    }
}

* Time Complexity: O(N)

* Space Complexity: O(1), return의 값으로  O(N)을 사용했지만, 그 이외는 따로 사용한 공간은 없다.

 

시작하기 전, list들을 linear time으로 reverse시킨 후, while loop을 돌리는 방식이다. 첫번째 리스트, 두번째 리스트를 reverse 하는데  M + N 번의 loop을 돌고, 숫자를 더하는 과정에서 max(M, N)의 시간이 든다. 그렇기 때문에 O(N)이라고 할 수 있다. 이 해법을 이용해서 최상위 속도와 중간정도의 않은 메모리 효율을 가졌다.

 

printList는 leetCode IDE에서 디버그 모드를 사용하려면 유료 전환을 해야해서, 디버그 용으로 사용했다. while loop 안에서 새로 생성한 결과값이 담긴 list를 보는 용도로 사용했었는데, 맨 앞자리 수가 나오지 않는 버그가 있었는데, while loop의 조건을 || 이 아닌 && 으로 했기 때문이었다. StringBuilder를 사용해서 mutable하게 스트링에 노드 값들을 붙여나갔고, 디버그용도이기때문에, 맨 마지막 노드도 쉼표를 붙였다. (실제라면, 맨 마지막 노드는 쉼표를 빼주는게 좋다).

 

 

 

이상해씨, 식스테일, 피카츄, 토게피, 고라파덕, 꼬부기,,, 꼬부기, 고라파덕, 토게피, 피카츄, 식스테일, 이상해씨,,,

 

Reference

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

Add Two Numbers II - LeetCode