乐趣区

关于数据结构和算法:LeetCode002两数相加medium

jiezi

题目：给出两个 非空 的链表用来示意两个 非负 的整数。其中，它们各自的位数是依照 逆序 的形式存储的，并且它们的每个节点只能存储一位数字。如果，咱们将这两个数相加起来，则会返回一个新的链表来示意它们的和。您能够假如除了数字 0 之外，这两个数都不会以 0 结尾

示例:

输出：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输入：7 -> 0 -> 8
起因：342 + 465 = 807

解题思路：

题中说各自的位数是依照逆序的形式存储到链表中，其实这升高了难度，因为刚好进行加法运算时，从个位开始加，而链表中从前到后是从低位开始的，刚好合乎了加法的运算程序（以题中给的数据为例）

既然是求和，那不难晓得，取出两个链表中的每一个节点，而后进行求和(sum)，如果大于 10 则记一个进位 1，而后拿 sum 对 10 进行求余，得的到后果就是指标链表的第一个无效节点，具体过程如图：

实现过程：

1、外围办法就是对两个链表进行遍历，而后一一节点求和

  • 因为不晓得这两个要求和的链表的节点个数(也就是不晓得循环次数)，所以抉择 while 循环。只有任何一个链表的节点不为 null，都须要持续进行循环
  • 然而因为有进位的状况，所以，当进位不是 0 时，也不能进行循环（比方 9999+1）

2、生成新的链表存储求和的后果

  • 对于链表的问题，通常都会创立一个标记节点，它不存具体的值，它的 next 负责指向第一个无效节点（始终指向第一个，不挪动），次要是为了不便咱们返回失去的指标链表
  • 同时须要创立一个 current 节点，他负责生成每一个节点，它是挪动的，每生成一个节点，它都须要向后挪动一个节点，从而实现构建新的链表

语言表达能力有点差，可能形容的不是很分明，代码中有必要的正文，心愿能够帮忙了解

代码实现

class ListNode
{
    public $val = 0;
    public $next = null;
    public function __construct($val)
    {$this->val = $val;}
}

class LeetCode002
{
    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    public function addTwoNumbers($l1, $l2)
    {if ($l1 == null && $l2 == null) {return null;}

        $tag = new ListNode(0);// 创立空节点
        $current = $tag;
        $addOne = 0;// 进位
        while ($l1 != null || $l2 != null || $addOne != 0) {
            $val1 = $l1 == null ? 0 : $l1->val;
            $val2 = $l2 == null ? 0 : $l2->val;
            $sum = $val1 + $val2 + $addOne;
            $current->next = new ListNode($sum % 10);
            $current = $current->next;
            $addOne = intval($sum / 10);// 坑，强类型语言不存在此问题
            if ($l1 != null) {$l1 = $l1->next;}
            if ($l2 != null) {$l2 = $l2->next;}
        }
        return $tag->next;
    }
}

//Test Case
$leetCode = new LeetCode002();
$l1 = new ListNode(2);
$l1->next = new ListNode(4);


$l2 = new ListNode(5);
$l2->next = new ListNode(6);

$newList = $leetCode->addTwoNumbers($l1, $l2);
$str = '';
while ($newList != null) {
    $str .= $newList->val.'->';
    $newList = $newList->next;
}

echo $str;

执行后果

退出移动版