6주차. 연결리스트(두 수의 덧셈)

16. 두 수의 덧셈

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

Add Two Numbers - LeetCode

📌문제
역순으로 저장된 연결 리스트의 숫자를 더하라.

- 예제1
  📝입력

l1 = [2,4,3], l2 = [5,6,4]

  💻출력

[7,0,8]

 - 예제2

  📝입력
 

l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

  💻출력
 

[8,9,9,9,0,0,0,1]

    
📌풀이
2ms, 42.3mb

/**
 * 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 answer = null;
        int temp = 0;
        while(l1 != null || l2 != null || temp > 0){
            int value1 = l1 != null ? l1.val : 0;
            int value2 = l2 != null ? l2.val : 0;
            int val = value1 + value2 + temp;
            temp = val/10;
            ListNode node = new ListNode(val%10);
            if(answer == null) answer = node;
            else{
                ListNode tempNode = answer;
                while(tempNode.next != null){
                    tempNode = tempNode.next;
                }
                tempNode.next = node;
            }
            if(l1 != null && l1.next != null) l1 = l1.next;
            else l1 = null;
            if(l2 != null && l2.next != null) l2 = l2.next;
            else l2 = null;
        }

        return answer;
    }
    
}

- 위 그림을 보면 어떻게 풀어야 할지 감이 올 것이다.

- 두 리스트를 같은 인덱스 끼리 더하면 정답이 나온다.

- 중요한 키포인트는 1번 인덱스 처럼 6+4 = 10, 즉 10 이상 일때, 이어지는 3+4에서 받아올림을 해주면 된다.

- 풀이법을 알고나니 연결리스트 중에서 제일 풀기 괜찮은 문제였다.