[LeetCode] 2. Add Two Numbers

Problem

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.

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]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Solution

Approach

1. l1, l2 노드의 값과 올림의 합을 값으로 가지는 노드를 생성하고 올림이 발생했다면 다음 계산을 위해 메모를 해둔다.

2. l1, l2 각 노드와 새로 생성한 노드가 다음 노드를 가리키도록 한다.

3. 위 과정을 l1, l2 노드가 null이고 올림 또한 발생하지 않은 시점까지 반복한다.

4. 새로 생성한 연결 리스트의 head노드를 반환한다.

Algorithm

Complexity Analysis

• Time Complexity

연결 리스트 l1의 길이를 q, l2의 길이를 p라 가정한다.

q와 p에 관계 없이 일정한 횟수로 실행되는 코드가 아닌 q와 p에 따라 증가하거나 감소하여 실행되는 코드는 6번째 줄의 while반복문이다.

while반복문이 실행되는 횟수는 (q와 p 중 큰 값) + 1회 실행되므로 본 알고리즘의 시간 복잡도는 O(max(q, p))이다.

• Space Complexity

연결 리스트 l1의 길이를 q, l2의 길이를 p라 가정한다.

q와 p에 관계 없이 일정한 공간을 할당받는 코드가 아닌 q와 p에 따라 증가하거나 감소된 공간을 할당받는 코드는 6번째 줄의 while반복문이다.

while반복문에 의해서 할당받는 공간은 (q와 p 중 큰 값) + 1이므로 본 알고리즘의 공간 복잡도는 O(max(q, p))이다.