[ Top Interview 150 ] 2. Add Two Numbers

문제

2. Add Two Numbers

  You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

  You may assume the two numbers do not contain any leading zero, except the number 0 itself.

• Input : singly-linked list 2개 각각의 head node
  • 모든 node의 val은 0 이상 9 이하의 정수
  • 각 노드는 앞의 node 부터 일의 자리, 10의 자리, 100의 자리, ...를 나타냄
  • 하나의 singly-linked list는 하나의 음이 아닌 정수를 나타냄
• Output : 새로운 singly-linked list의 head node
  • 두 singly-linked list가 나타내는 수를 더하여, 해당 수를 나타내는 singly-linked list를 만들기
• Example
  • Input: l1 = [2,4,3], l2 = [5,6,4]; Output: [7,0,8]
    • Explanation: 342 + 465 = 807.
  • Input: l1 = [0], l2 = [0]; Output: [0]

알고리즘 전략

• 기본 전략

  1. 새로운 singly-linked list를 만든다.
  2. 일의 자리 수부터 더해서 계산 결과를 Node에 넣는다.
  3. 계속 다음 노드로 넘어가서 반복한다.

• 받아올림 전략 (다음 노드 만들기 전략)

  1. 현재 노드의 val 값이 10 이상일 경우, 다음 노드의 초기값을 1로 한다. 그리고 현재 노드는 10을 뺀다.
  2. 현재 노드의 val 값이 10 미만일 경우, 다음 노드의 초기 값을 0으로 한다.
  • 해당 기능이 반복적으로 쓰일 것을 예상하여, 다른 method로 분리하여 구현

1차 답안

• Time complexity : O(n)
• Space complexity: O(n)

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(l1.val + l2.val);
        l1 = l1.next; l2 = l2.next;
        ListNode currentNode = head;

        while (l1 != null || l2 != null) {
            currentNode = makeNextNode(currentNode);
            if (l1 != null) {
                currentNode.val += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                currentNode.val += l2.val;
                l2 = l2.next;
            }
        }

        if (currentNode.val >= 10) {
            currentNode = makeNextNode(currentNode);
        }

        return head;
    }

    private ListNode makeNextNode(ListNode tailNode) {
        ListNode nextNode = new ListNode(tailNode.val / 10);
        tailNode.val %= 10;
        tailNode.next = nextNode;
        return nextNode;
    }
}

/**
 * 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; }
 * }
 */