[LeetCode] 2. Add Two Numbers

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

개요

1. 두개의 링크드 리스트가 주어진다.
   • 두 개의 링크드 리스트는 길이가 다를 수 있다.
   • 길이가 다르다면, 자릿수가 다른 경우라고 생각하면 된다.
2. 두개의 링크드 리스트를 더하기 연산해라.
   • 각 인덱스의 노드에서 올림수가 발생할 수 있다
   • ex> l1 = [2,4,3], l2 = [5,6,4], output = [7,0,8]
3. 더하기 연산한 결과를 LinkedList에 저장하고, 그 head 노드를 반환하라.

문제 해결 아이디어

• 올림수를 다음 인덱스 연산할때 더해 덧셈의 올림을 구현하자.
• 두 개의 링크드 리스트가 모두 tail 일 때까지 연산이 진행되어야 한다.

의사 코드

1. head 노드 value 들을 더하기 연산해, answer 노드에 저장한다.
2. l1, l2 노드를 옮기기
3. l1, l2 노드 value 들을 더하기 연산해, answer 다음 노드를 생성하기
4. while 문을 돌고 남은 carry가 있다면 노드 추가
5. answer 노드의 head 노드 반환

head 노드
answer 노드 = head 노드
digit = (l1.value + l2.value)
do answer 노드.value = sum
l1 = l1.다음노드
l2 = l2.다음노드
while(l1 != null || l2 != null){
	digit = (l1.value + l2.value) + 넘어온 carry
    carry = sum/10
    digit = digit%10
    answer 노드 = answer노드.next
    answer 노드 = new 노드(digit)
}
if(carry > 0) {
	 answer노드.next = new 노드(carry)
}

결과

전체 코드 github 링크

다른 풀이

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode temp = new ListNode(0);
        ListNode fakeHead = temp;
        int carry = 0;
        int digit = 0;
        while (l1 != null || l2 != null) {
            digit = carry;
            if (l1 != null) {
                digit += l1.val;
                l1 = l1.next;
            }

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

            carry = digit / 10;
            digit = digit % 10;
            temp.next = new ListNode(digit);
            temp = temp.next;
        }

        if(carry > 0) temp.next = new ListNode(carry);
        return fakeHead.next;
    }

연산 결과가 없는 경우 노드가 생성되면 안되기 때문에,
각 인덱스에 대해 연산할 때마다 새로운 노드가 만들어져야 한다.
그런데 head노드는 따로 저장하고 반환하기도 해야해서 별도 처리가 필요하다.
그래데 나는 head 노드를 while문 밖에서 별도로 처리하느라 코드가 굉장히 더러워졌는데,
위 코드처럼 fakeHead 를 일단 만들어서 head 노드도 동일한 while문 안에서 처리하는 방식이 아주 좋은 것 같다.
이 head 노드에 대한 처리 때문에 고전했던 문제이지만, linked list에 대한 좋은 접근 방식 알게 된 것 같아 좋다.