LeetCode #2: Add Two Numbers

Original problem

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

Original text

Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, 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 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

Example 2

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

Example 3

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

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.

Additional information provided

/**
 * 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;
 *     }
 * }
 */

/**
 * @param ListNode $l1
 * @param ListNode $l2
 * @return ListNode
 */

Solution (PHP 8.2)

Notes

class ListNode {
    public function __construct(
        public int $value = 0,
        public ?self $nextNode = null
    ) {}
}

ListNodeAdder::add(
    ListNodeFactory::arrayToChain([9,9,9,9,9,9,9]),
    ListNodeFactory::arrayToChain([9,9,9,9]),
);

class ListNodeAdder {
    protected int $buffer = 0;

    public static function add(?ListNode $x, ?ListNode $y): ListNode
    {
        return (new self())->addRecursive($x, $y);
    }

    protected function addRecursive(
        ?ListNode $x,
        ?ListNode $y,
        ?ListNode $result = null
    ): ?ListNode {
        if (null === $x && null === $y) {
            if ($this->buffer > 0) {
                ListNodeFactory::enchain($result, $this->buffer);
            }

            return $result;
        }

        ListNodeFactory::enchain($result, $this->calculate(
            static::getNodeValue($x),
            static::getNodeValue($y)
        ));

        return $this->addRecursive( // ↻ Recursion!
            static::getNextNode($x),
            static::getNextNode($y),
            $result // Passed as symbolic link
        );
    }

    protected function calculate(int $x, int $y): int
    {
        $result = $x + $y;

        if (0 !== $this->buffer) {
            $result += $this->buffer;
            $this->buffer = 0;
        }

        if ($result >= 10) {
            $result -= 10;
            $this->buffer = 1;
        }

        return $result;
    }

    protected static function getNodeValue(?ListNode $listNode): int
    {
        if ($listNode instanceof ListNode) {
            return $listNode->value;
        }

        return 0;
    }

    protected static function getNextNode(?ListNode $listNode): ?ListNode
    {
        if ($listNode instanceof ListNode) {
            return $listNode->nextNode;
        }

        return null;
    }
}

class ListNodeFactory
{
    public static function arrayToChain(array $items): ?ListNode
    {
        $list = null;
        foreach ($items as $item) {
            static::enchain($list, $item);
        }

        return $list;
    }

    public static function enchain(?ListNode &$listNode, int $value): void
    {
        if (null === $listNode) {
            $listNode = new ListNode($value);

            return;
        }

        if ($nextNode = $listNode->nextNode) {
            static::enchain( // ↻ Recursion!
                $nextNode, // Passed as symbolic link
                $value
            );

            return;
        }

        $listNode->nextNode = new ListNode($value);
    }
}

Tests

List X	List Y	Result	Time	Memory
`[2,4,3]`	`[5,6,4]`	`[7,0,8]`	482μs	1112B
`[0]`	`[0]`	`[0]`	482μs	1112B
`[9,9,9,9,9,9,9]`	`[9,9,9,9]`	`[8,9,9,9,0,0,0,1]`	205μs	2192B

OS: Ubuntu WSL2 (5.15.146.1-microsoft-standard-WSL2)
CPU: AMD Ryzen 7 5800X
RAM: 16GB

PHP 8.2.17 (cli) (built: Mar 16 2024 08:41:44) (NTS)
Copyright (c) The PHP Group
Zend Engine v4.2.17, Copyright (c) Zend Technologies
    with Zend OPcache v8.2.17, Copyright (c), by Zend Technologies
    with Xdebug v3.3.1, Copyright (c) 2002-2023, by Derick Rethans

memory_limit => -1
xdebug.mode => profile

Description#

Example 1#

Example 2#

Example 3#

Constraints#

Additional information provided#

Solution (PHP 8.2)#

Tests#