402v

最近在刷leetcode，对自己的算法思路做个简单的记录，希望最后回顾起来自己是有提高的。

通篇算法都是用Ruby语言实现，文内不再赘述。Markdown没有支持数学格式，所以时间复杂度的记法比较粗糙，见谅。

这一系列的文章可以在这里找到。

本期题目:

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

题目难度：中级

这道题刚开始没看懂。。。题目的意思是给两个链表分别代表两个非负数。数字的每一位按照逆序存储在链表的每个结点中。将这两个非负数相加同时返回一个相同结构的链表。

###多些时间可以少些Code 链表、数字相加，显然是一道考察编程的题，所以就越是要小心边界条件、逻辑分支。

反向链表的好处是从头结点直接相加，大等于10则下一位加一；
由于是非负整数，所以我们可以认为链表中至少有一个结点是有值的，这样就省去了很多麻烦；
题目没说是不是非负整数，姑且先按整数考虑，submit的时候跑case看看；
当其中一个链表走到头时，另一个链表剩余的位数可以直接拼接到结果链表中。注意如果之前一个相加刚好大等于10则需要剩余位数的第一位加一，后续几位也同理（如：234 + 34669991）；
如果相加之后的最后一位大等于10，结果链表长度会等于两个链表长度的最大值加一，（如：333 + 667）

###还是要Code

一次提交成功！代码如下：

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val)
#         @val = val
#         @next = nil
#     end
# end

# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def add_two_numbers(l1, l2)
    decimal = 10 # 十进制
    
    carrybit = 0 # 进位标识符
    
    # 初始化结果链表头结点，个位相加
    sum_val = l1.val + l2.val
    l1 = l1.next
    l2 = l2.next
    
    carrybit = sum_val/decimal
    sum_val = sum_val%decimal
        
    sum_list = ListNode.new(sum_val)
    current_node = sum_list
    
    # 链表元素相加
    while l1 || l2 do
        sum_val = carrybit
        
        if l1 then
            sum_val += l1.val
            l1 = l1.next
        end
        
        if l2 then
            sum_val += l2.val
            l2 = l2.next
        end
        
        carrybit = sum_val/decimal
        sum_val = sum_val%decimal
        
        current_node.next = ListNode.new(sum_val)
        current_node = current_node.next
    end
    
    # 最后一位是否有进位？
    if carrybit > 0 then
        current_node.next = ListNode.new(carrybit)
        current_node = current_node.next
    end
    
    sum_list
end

在实现上经过了几个优化：

之前把l1或l2剩余结点的情况用单独的while处理，后来发现放到一个while里面做下if判断就好；
```
 if l1 then
     sum_val += l1.val
     l1 = l1.next
 end
```

用求余和取整代替用if判断是否需要进位；

 carrybit = sum_val/decimal
 sum_val = sum_val%decimal

将代表进制的变量单独抽离处理，初步看16进制和其他进制也可以用这个函数处理。
```
 decimal = 10 # 十进制
```

此题为第二题。

LeetCode实战 - Add Two Numbers

评论 · 0