[Java] 2. Add Two Numbers

문제 파악

비어있지 않은 두개의 연결 리스트가 주어진다.

 

음수가 아닌 정수의 숫자를 역순으로 연결리스트에 보관되어있다.

 

ex. 342 인 경우 연결리스트에 [2] -> [4] -> [3] 으로 구성

 

연결리스트로 표현되는 두 정수의 합을 동일한 방식으로 연결리스트로 반환해야한다.

 

---

풀이

 

1️⃣ 

💡 떠오른 Idea

l1의 val과 l2의 val을 더하고 10으로 나눈 몫과 나머지를 구한다.

10으로 나눈 몫은 다음 노드들의 val 합에 더해주어야 한다.

나머지를 통해 노드 클래스를 만들어 이전 노드의 next 노드로 연결해준다.



그리고, l1 과 l2의 길이가 다를 수 있다.

따라서, l1 과 l2가 둘다 null이 아니라면 로직을 계속 수행해야한다.

또한, 몫으로 넘어온 값이 있는 경우 노드를 추가로 생성해주어야 하기 때문에 이 부분도 조건문에 추가한다.

 

위 아이디어를 바탕으로 코드를 구현하였다.

 

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int q = 0;
        int r = 0;
        ListNode start = new ListNode();
        ListNode node = start;
        while (l1 != null || l2 != null || q != 0) {
            int sum = q;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            q = sum / 10;
            r = sum % 10;

            node.next = new ListNode(r);

            node = node.next;
        }

        return start.next;
    }
}

 

결과

---

📖 회고

연결 리스트를 간접적으로 활용한 적은 많았지만, 이런식으로 노드 클래스가 주어지고

 

문제를 해결한 적은 거의 없어서, 생각보다 오래 고민하게 되었다.

 

이번 문제를 풀기 위해서, 연결 리스트의 원리에 대해 더욱 깊숙히 고민하게 되어 좋은 문제였다고 생각이 든다.