leetcode 445번문제 add two numbers 2

문제

add two numbers의 문제와 같지만 이번엔 역순으로 저장되어있지 않다.

 

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 8 -> 0 -> 7

 

/**
 * 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) {
       int checkNum = 0;
        Stack<Integer> stackL1 = new Stack<Integer>();
        Stack<Integer> stackL2 = new Stack<Integer>();
        
        while (l1 != null) {
            stackL1.add(l1.val);
            l1 = l1.next;
        }
        
        while (l2 != null) {
            stackL2.add(l2.val);
            l2 = l2.next;
        }
        
        ListNode dummy,result = new ListNode(0);
        
        dummy = result;
        
        while (stackL1.size() != 0 || stackL2.size() != 0 || checkNum != 0) {
            
            if (stackL1.size() != 0) {
                checkNum += stackL1.pop();
            }
            
            if (stackL2.size() != 0) {
                checkNum += stackL2.pop();
            }
            
            dummy.val = checkNum % 10;
            
            dummy = new ListNode(0);
            dummy.next = result;
            result = dummy;
            
            checkNum /= 10;        
            
        }
 
        return result.next;
    }
}

 

시간복잡도 O (n log n)

 

1.각각의 스택에 매개변수로받은 l1,l2를 집어넣는다.

2. 1번문제와 같이 담을 listnode 생성

3. stack은 pop을 사용할경우 마지막에 넣엇던 값을 출력하며 스택에 담긴 값을 지운다.

4. 39번줄 dummy.val에 stack에서 뽑아낸값을 저장한후 10으로 나눈 나머지를 저장

5. 45번 checkNum에는 10으로 나눈 몫을 저장

6. dummy에 새 listnode인스턴스를 생성한 후 dummy.next dummy의 하위에 result 주소를 담는다.

7. 다시 result에는 dummy주소를 담는다.

8. 이렇게되면 result는 0이 생성되어있고 하위노드는 아까 checkNum으로 나눈 나머지가 저장되어있다.

9. 이런식으로 하위부터 상위를 만들어나간다.

10. 스택에서 뽑아낸값을 썼으므로 하위부터 상위로 만들면 똑바로 나옴

11. 스택을 사용한 이유는 노드는 앞자리 숫자부터 등록되어있기 떄문에 자릿수 연산에 불편함이 있으므로

    스택을 사용하여 편하게 일의 자리숫자부터 연산을 함 

12. while 조건이 끝나면 return