2. 两数相加

题意

解题思路:

思路：

• 从低位到最高位，逐位相加，如果和大于等于10，则保留个位数字，同时向前进一位
• 如果最高位有进位，则需在最前面补1
• 时间复杂度是 O(n).

PHP 代码实现

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {
    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        $add = 0; //表示进位
        $head = new ListNode(0);//添加虚拟头结点，简化边界情况的判断
        $curr = $head;
        while ($l1 != null || $l2 != null || $add != 0) {
            $sum = $add;
            if ($l1 != null) {
                $sum += $l1->val;
                $l1 = $l1->next;
            }
            if ($l2 != null) {
                $sum += $l2->val;
                $l2 = $l2->next;
            }
            $curr->next = new ListNode($sum % 10);//如果最高位有进位，则需在最前面补1.
            $curr = $curr->next;
            $add = intval($sum / 10);
        }
        return $head->next;
    }
}

GO 代码实现

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    headList := new(ListNode)
    head := headList
    num := 0
    for (l1 != nil || l2 != nil || num > 0) {
        headList.Next =  new(ListNode)
        headList = headList.Next
        if l1 != nil {
            num = num + l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            num = num + l2.Val
            l2 = l2.Next
        }
        headList.Val = (num) % 10
        num = num / 10 
    }
    return head.Next
}