[LeetCode] 2. Add Two Numbers

Add Two Numbers - LeetCode

두개의 Linked list가 주어집니다.

Linked list는 reverse order인 상태로 주어지고

두개의 Linked list의 합을 구하는 문제입니다. 

 

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

문제 접근

재귀 함수를 사용해 linked list 각각의 수를 더하고

새로운 노드를 만들어 반환하였지만  문제의 요구사항을 완벽히 만족하지 못했습니다.

 

여러 시도를 해보았지만 답을 모르겠어서 검색을 통해 답을 확인하였습니다.

 

다른사람의 풀이

재귀함수를 이용해 값을 확인하고 더한 후 1의자리수만 노드에 추가하고

10의자리수는 carry에 보관하여 다음에 추가하는 로직입니다.

 

재귀

int carry = 0;
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        if (l1 == null && l2 == null && carry == 0) {
            return null;
        }
        
        int val1 = l1 == null ? 0 : l1.val;
        int val2 = l2 == null ? 0 : l2.val;
        
        int sum = val1 + val2 + carry;
        carry = sum/10;
        
        l1 = l1 == null ? null : l1.next;
        l2 = l2 == null ? null : l2.next;
        
        ListNode ans = new ListNode(sum%10, addTwoNumbers(l1, l2));
        
        return ans;
    }

 

while

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

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

            carry=sum/10;
            sum %=10;
            head.next = new ListNode(sum);
            head = head.next;
        }
    return temp.next;
    }

 

느낀점

재귀함수를 잘 활용하려면 재귀 호출시 stack을 더 깊이 연구해보아야 할것 같습니다.

모범답안의 클린한 코드를 보고 한없이 작아졌습니다...

부족한 만큼 많이 공부하고 배워야겠다는 생각이 들었습니다😁 

 

참고

Java 1ms Recursive Solution, 1ms, Faster than 100% - Add Two Numbers - LeetCode