LeetCode: Add Two Numbers

Bài toán

https://leetcode.com/problems/add-two-numbers/

Giải pháp

Tạo 1 linked list mới. Trong khi $l1 hoặc $l2 hoặc số dư $carry là true (khác null hoặc khác 0) thì tính tổng.

Node tiếp theo sẽ có giá trị là tổng trên % 10.

$carry mới sẽ là tổng trên / 10 (ép kiểu về int)

Code PHP

/**
 * 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) {
        $dummy = new ListNode();
        $current = $dummy;
        $carry = 0;

        while(!is_null($l1) || !is_null($l2) || $carry !== 0) {
            $x = $l1?->val ?? 0;
            $y = $l2?->val ?? 0;

            $sum = $x + $y + $carry;

            $carry = (int)($sum / 10);
            $current->next = new ListNode($sum % 10);
            $current = $current->next;

            if ($l1 !== null) {
                $l1 = $l1->next;
            }

            if ($l2 !== null) {
                $l2 = $l2->next;
            }
            
        }

        return $dummy->next;
    }
}

Độ phức tạp

Time complexity: O(max(m, n)) Trong đó m và n là độ dài list $l1 và $l2

Space complexity: O(1) - Linked List có độ phức tạp O(1)