445. Add Two Numbers II

445. Add Two Numbers II

Medium

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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 = [7,2,4,3], l2 = [5,6,4]
• Output: [7,8,0,7]

Example 2:

• Input: l1 = [2,4,3], l2 = [5,6,4]
• Output: [8,0,7]

Example 3:

• Input: l1 = [0], l2 = [0]
• Output: [0]

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.

Follow-up: Could you solve it without reversing the input lists?

Solution:

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        $s1 = new SplStack();
        $s2 = new SplStack();
        while($l1 != null){
            $s1->push($l1->val);
            $l1 = $l1->next;
        }

        while($l2 != null){
            $s2->push($l2->val);
            $l2 = $l2->next;
        }

        $sum = 0;
        $cur = new ListNode();
        while(!$s1->isEmpty() || !$s2->isEmpty()){
            if(!$s1->isEmpty()) $sum += $s1->pop();
            if(!$s2->isEmpty()) $sum += $s2->pop();

            $cur->val = $sum%10;
            $head = new ListNode(floor($sum/10));
            $head->next = $cur; // reconstruct
            $cur = $head;// moving on
            $sum /= 10;
        }
        if($cur->val >= 1 ){
            $return_value =  0? $cur->next: $cur;   
        }else{
            $return_value = $cur->next;
        }
        return ($return_value);
        //return $cur->val == 0? $cur->next: $cur;
    }
}

Contact Links

• LinkedIn
• GitHub