反璞歸真 DFS模擬鏈結串列的四則運算。 Leetcode #2816

Crissy Jarvis on Unsplash

題目敘述

輸入給定一個鏈結串列，整體看代表一個十進位的數字，各別看每個節點代表每個digit，分別從最高位~最低位個位數。

要求我們把原本的數字乘以二，並且以鏈結串列的形式返回答案。

測試範例

Example 1:

Input: head = [1,8,9]
Output: [3,7,8]
Explanation: The figure above corresponds to the given linked list which represents the number 189. Hence, the returned linked list represents the number 189 * 2 = 378.

Example 2:

Input: head = [9,9,9]
Output: [1,9,9,8]
Explanation: The figure above corresponds to the given linked list which represents the number 999. Hence, the returned linked list reprersents the number 999 * 2 = 1998. 

約束條件

Constraints:

• The number of nodes in the list is in the range [1, 10^4]

節點總數目介於 1 ~ 一萬之間。

• 0 <= Node.val <= 9

每個節點值都介於0~9之間。

• The input is generated such that the list represents a number that does not have leading zeros, except the number 0 itself.

題目保證不會有leading zero。

演算法 DFS模擬直覺算法

反璞歸真，其實用DFS模擬平常我們四則運算的方式就可以了。

某個數字乘以二，會怎麼做?

就是用二去乘以每一位，從個位數 ~ 最高位。

實作上有一個細節要留意:
計算的時候，記得有進位時，要傳遞到下一個比較高的位數。

程式碼 DFS模擬直覺算法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # Our calculation naturally goes from LSB to MSB, aka from right to left
        # This fits the property of DFS + recurion with Last In - First Oout
        # We add carryIn and multiply 2 from single digit, tenths, hundreds, ... to leading digit
        def compute(node):
            
            ## Base case: Empty node = termination
            if not node:
                return 0, None
            
            # Compute from right to left
            carryIn, neighbor_node = compute(node.next)

            # Connect next digit
            node.next = neighbor_node

            # Handle carryIn and current digit sum with x 2
            carryIn, digit = divmod( (node.val << 1) + carryIn , 10)
            node.val = digit

            # Propogate carryIn and myself to lefthand side
            return carryIn, node

        # --------------------------------

        # Get leading term
        carryIn, node = compute(head)

        # Do we have carryIn after x 2 ?
        # If yes, then carryIn is new leading term.
        if carryIn:
            return ListNode(carryIn, node)
        
        # If no, then original head node is leading term.
        else:
            return node

複雜度分析

時間複雜度: O(n)

從個位數 計算到 最高位，每一位都進行乘以二的計算，並且把進位傳到下一個比較高的位數。

空間複雜度: O(n)

最大遞迴深度剛好就是有幾位數，n位數的數字最深遞迴深度恰好為O(n)。

關鍵知識點

某個數字乘以二，會怎麼做?

就是用二去乘以每一位，從個位數 ~ 最高位。

實作上有一個細節要留意:

計算的時候，記得有進位時，要傳遞到下一個比較高的位數。

Reference

[1] Double a Number Represented as a Linked List - LeetCode