2. 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 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.

https://leetcode.com/problems/add-two-numbers/?envType=study-plan-v2&envId=top-interview-150

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

 import java.math.*;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s;
        ListNode node;
        
        s = new Stack<>();
        node = l1;
        while(true) {
            s.push(node.val);
            node = node.next;

            if (node == null) {
                break;
            }
        }

        StringBuilder sb1 = new StringBuilder();
        while(!s.isEmpty()) {
            sb1.append(s.pop());
        }


        //

        s = new Stack<>();
        node = l2;
        while(true) {
            s.push(node.val);
            node = node.next;

            if (node == null) {
                break;
            }
        }

        StringBuilder sb2 = new StringBuilder();
        while(!s.isEmpty()) {
            sb2.append(s.pop());
        }

        BigInteger num1 = new BigInteger(sb1.toString());
        BigInteger num2 = new BigInteger(sb2.toString());
        BigInteger sum = num1.add(num2);

        String get = sum + "";
        char[] c = get.toCharArray();

        ArrayList<ListNode> list = new ArrayList<>();

        for (int i = 0; i < c.length; i++) {
            list.add(new ListNode());
        }

        for (int i = c.length - 1; i >= 0; i--) {
            ListNode nowNode = list.get(i);
            nowNode.val = c[i] - '0';

            if (i == 0) {
                nowNode.next = null;
            } else {
                nowNode.next = list.get(i - 1);
            }
        }

        return list.get(list.size() - 1);
    }
}

// 먼저, 역순으로 찾아야하기 때문에 stack을 쓰자. [2, 4, 3] -> 342

주어진 두 개의 연결리스트 들의 값을 역순으로 두어 (2, 4, 3 -> 342) 합 연산한 결과를 다시 하나의 연결리스트로 구하는 문제였다.

Stack을 활용하여 연결리스트의 역순을 저장한 뒤, LIFO 형식으로 pop한 값들을 StringBuilder에 추가하여 String 형태로 관리하였다. (문자열을 합 연산 하였기 때문에 메모리 이슈가 있을수 있어 StringBuilder 활용)

이후에는 Integer.parseInt(String)을 통해 정수형으로 변환하여 합 연산을 진행했지만 overflow가 발생하여 BigInteger를 통해 합 연산을 진행했다.

아래와 같이 각각의 자리수마다 따로 합 연산을 하여 초과되는 값 (10이상인 경우) 에는 다음 연산으로 넘기는 방식도 활용할 수 있었지만 귀찮아서 하지않았다..

  3 4 2
+ 4 6 5
---------
	  7
  1 0
  7
========= 
  8 0 7  - ans