[Algorithm] LeetCode - 2. Add Two Numbers (LinkedList, Math, Recursion)

 

LeetCode 문제입니다.

[문제설명]

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.

 

번역)

두 개의 음이 아닌 정수를 나타내는 두 개의 비어 있지 않은 연결 목록이 제공됩니다. 
숫자는 역순으로 저장되며 각 노드에는 단일 숫자가 포함됩니다. 두 숫자를 더하고 합을 연결 목록으로 반환합니다.
숫자 0 자체를 제외하고 두 숫자에 선행 0이 포함되어 있지 않다고 가정할 수 있습니다.

 

Topic: Linked List, Math, Recursion

Level: Medium

Accepted 2,881,236 / Submissions 7,392,660

---

[제한사항]

 

• 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.

 

---

[입출력]

예시 1

 

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

 

예시 2

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

 

예시 3

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

---

[문제풀이]

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const addTwoNumbers = (l1, l2) => {

    let sumNode = new ListNode()
    
    const recursiveFunc = (_l1, _l2, _l3) => {
        // terminate if one of list node is empty(ends)
        if (!_l1 && !_l2) return
   
        const paramOne = _l1 ? _l1.val : 0
        const paramTwo = _l2 ? _l2.val : 0
        const paramThree = _l3.val
        const sum = paramOne + paramTwo + paramThree
        
        // set reamin value,         
        _l3.val = sum%10
        // set value when sum is equal or more than 10
        if (sum >= 10){
            _l3.next = new ListNode(1)
        } else if (_l1?.next || _l2?.next) {
            _l3.next = new ListNode()
        }
    
        recursiveFunc(_l1?.next, _l2?.next, _l3?.next)
    }

    recursiveFunc(l1, l2, sumNode)
    
    return sumNode

};

Failure: 

첫번째 코드에서 보기 좋게 time limit이 걸렸다.

topic이 hash인것도 모르고 무식하게 array에서 linear search를 했기 때문!

time limit이 난 input을 보니 strs 배열의 item들이 대부분 문자열 크기가 다르고 grouping되는 아나그램이 거의 없었다.

따라서 linear search만 하다가 time complexity에서 꽝이 난것.

 

 

Idea: 

1. LinkedList 연산이니 recursiveFunc을 통해서 iterator을 직접 해야 한다.

2. sum이 10과 같거나 크면 sumNode의 next를 맞춰주어야 한다.

3. 다음 iteration 조건이 되지 않는 경우 next node를 설정하지 않아야 padding 0가 생기지 않는다.

---

 

[Performance]