欣迪

出處: https://leetcode.com/problems/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.

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.

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

var addTwoNumbers = function(l1, l2) {     
    let temp = 0;
    const head = new ListNode()
    let node = head
    while(l1 || l2) {
        let sum = temp
        if (l1 !== null) {
            sum += l1.val
            l1 = l1.next
        }
        if (l2 !== null) {
            sum += l2.val
            l2 = l2.next
        }
        
        if (sum >= 10) {
            temp = 1
            sum = sum - 10
        } else {
            temp = 0
        }        
        node.next = new c(sum)
        node = node.next        
    }
    if (temp === 1) {
        node.next = new ListNode(1)
    }
    return head.next
};

思路

這題如果做過基本的 Linked List 題目,應該不難。建議先把以下這幾題搞懂:

  1. 解題 30. Design Linked List (節點鏈)
  2. 解題 31. Reverse Linked List (反轉 Linked List)
  3. 解題 35. Palindrome Linked List

首先,這邊 input 的 linked list 已經是從個位數開始往下連結。所以不需要知道整個 list 的全貌即可開始處理。

將兩個 l1 和 l2 的 val 相加,由於題目已經規範數字是在 1 ~ 9 之間,所以兩數相加最大值不過 18 (兩個 val 都是 9),因此如果兩數的和 sum 超過 10,則把 1 帶入下一個階段。

等到 l1, l2 都已經跑完變成 null ,在檢查最後一次相加是否超過 10 。如果超過,要再補一個 val 為 1 的 ListNode

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。