[LeetCode/Java] 2. Add Two Numbers

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

 

알고리즘 문제를 풀다 보면, 가끔은 나도 모르게 ‘답만 나오면 된다’는 식으로 접근할 때가 있다.
그런데 이번 문제를 풀면서 Linked List라는 자료구조의 본질적인 구조와 연결 방식을 다시 생각하게 됐다.
단순한 구현 문제처럼 보여도, 기초를 다지는 데 정말 좋은 문제였던 것 같다.
그래서 이 문제는 그냥 넘기지 않고, 블로그에 기록해두기로 🤭

 

[문제 간단 요약]

두 개의 역순으로 저장된 Linked List가 있고, 각 노드는 한 자리 숫자를 담고 있다.

이걸 실제 정수처럼 더해서, 결과를 똑같이 역순 Linked List로 리턴하기

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

---

💡 문제에서 말하는 ListNode가 뭘까?

이건 LeetCode가 연결 리스트(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;
    }
}

 

쉽게 말하면,

val: 노드가 들고 있는 숫자

next: 다음 노드를 가리키는 포인터 (없으면 null)

---

자바에서 연결 리스트 만들기!

예를 들어 (2 -> 4 -> 3) 이라는 연결 리스트를 만들고 싶다면?

ListNode node1 = new ListNode(2);
ListNode node2 = new ListNode(4);
ListNode node3 = new ListNode(3);

node1.next = node2;
node2.next = node3;

// node1이 head (시작 노드)

• 이렇게 연결하면 node1이 2->4->3 이라는 연결 리스트의 시작이 된다.

---

이걸 바탕으로 그러면 문제는 어떻게 풀 수 있을까?

두 개의 ListNode (l1, l2)가 있을 때, 각각의 숫자를 한 자리씩 더하면서 carry(올림수)를 관리해주면 된다.

결과도 ListNode형태로 만들어서 반환해 주면 완료

---

✔️ 문제 풀이 보기

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode curr = head;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;

            int sum = val1 + val2 + carry;
            carry = sum / 10; // 올림수
            int digit = sum % 10; // 현재 자리수

            curr.next = new ListNode(digit);
            curr = curr.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        } 

        return head.next;
    }
}

---

✔️ 풀이 해설 보기

1. 임시 노드 만들기

ListNode head = new ListNode(0);
ListNode curr = head;

• head : 결과 연결 리스트를 만들기 위한 임시 시작 노드
  => 나중에 head를 따로 기억하지 않아도 되게 하려고 사용
• curr : 결과 리스트를 쭉 연결하면서 앞으로 가는 포인트

   => 결과 리스트는 head.next 부터 시작한다는 것을 꼭 기억하기

2. 반복문 조건

while (l1 != null | l2 != null | carry != 0)

• 한 쪽 리스트가 끝나더라도 나머지가 남아있을 수 있으니까
  carry != 0 까지 체크해야 마지막에 올림이 남아있는 것도 처리가 가능

3. 각 자리 숫자 꺼내기

int val1 = (l1 != null ? l1.val : 0);
int val2 = (l2 != null ? l2.val : 0);

• 리스트가 짧아서 null이 됐을 수도 있으니, null이면 0으로 처리해줌

4. 더하고 올림 처리

int sum = val1 + val2 + carry;
carry = sum / 10;
int digit = sum % 10;

• sum : 자리값 끼리 더하고 이전 carry도 포함
• carry : 다음 자리로 넘길 값(10 이상이면 1, 아니면 0)
• digit : 현재 자리에 들어갈 값(한 자리 숫자)

   예시) 4 + 6 + 1 = l1 -> carry = 1, digit = 1

5. 결과 연결 리스트에 노드 추가

curr.next = new ListNode(digit);
curr = curr.next;

• 새로운 노드를 만들고 연결
• 포인터를 다음으로 옮겨서 다음 자리 준비

 

6. l1, l2 포인터 이동

if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;

• 각각 다음 자리로 이동

 

7. 결과 반환

return head.next;

• head는 더미니까 버리고, 그 다음부터가 진짜 결과