LeetCode-2. Add Two Numbers

LeetCode-2. Add Two Numbers

難度: medium

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.

解題流程

1. 先看懂題目想描述甚麼情境
2. 開始想像程式運作該經過哪些流程
3. 將經過的流程所需的判斷跟細節列出
4. 實作列出的流程

先看懂題目想描述甚麼情境

開始想像程式運作該經過哪些流程

將經過的流程所需的判斷跟細節列出

實作列出的流程

typescript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const result = new ListNode(0);

    let head = result;
    let lastDigit = 0;
    while(l1 || l2 || lastDigit) {
        const tempNode = new ListNode(lastDigit);
        head.next = tempNode;

        let l1Val = 0;
        let l2Val = 0;

        if(l1) {
            l1Val = l1.val;
            l1 = l1.next;
        }

        if(l2) {
            l2Val = l2.val;
            l2 = l2.next;
        }

        let nextHeadVal = l1Val + l2Val + tempNode.val;
        if(nextHeadVal >= 10) {
            head.next.val = nextHeadVal - 10;
            lastDigit = 1;
        } else {
            head.next.val = nextHeadVal
            lastDigit = 0
        }
        head = head.next;
    }
    return result.next;
};

更好的方法

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const result = new ListNode(0);

    let head = result;
    let lastDigit = 0;
    while(l1 || l2) {

        let l1Val = 0;
        let l2Val = 0;

        if(l1) {
            l1Val = l1.val;
            l1 = l1.next;
        }

        if(l2) {
            l2Val = l2.val;
            l2 = l2.next;
        }

        let nextHeadVal = l1Val + l2Val + lastDigit;
        lastDigit = Math.floor(nextHeadVal/10);
        const nextNode = new ListNode(nextHeadVal%10);
        head.next = nextNode;
        head = head.next;
    }

    if(lastDigit) {
        const nextNode = new ListNode(lastDigit);
        head.next = nextNode;
    }
    return result.next;
};

感謝閱讀，如果有錯誤或是講得不清楚的部分，再請留言指教