关于leetcode:LeetCode-题解与知识点-2-两数相加-AddTwoNumbers

题目链接

2. Add-Two-Numbers 难度：$\color{#00965e}{medium}$

知识点

1. 数据结构单链表

数据结构根底，此处不赘述

2. 链表尾插法

C 单链表头插法 / 尾插法 / 删除指定值结点

解法

简略累加

• 留心进位
• 用 head 记录头结点，head->next 即题解须要的头结点

复杂度剖析

• 工夫复杂度：O(max(m,n))，其中 m,nm,n 为两个链表的长度。咱们要遍历两个链表的全副地位，而解决每个地位只须要 O(1)O(1) 的工夫。
• 空间复杂度：O(max(m,n))，答案链表的长度最多为较长链表的长度 +1+1。

以下为 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) {
        $carry      = 0;
        $tmp_int    = 0;
        $head       = new ListNode();
        $end        = new ListNode();
        $end        = $head;
        //$head     = $end;// 与下面的写法其实是一样的，这里的 head 是保留了头结点
        while($l1 !=NULL || $l2!=NULL || $carry > 0){if ($l1 != NULL){
                $tmp_int += $l1->val;
                $l1       = $l1->next;
            }
            if ($l2 != NULL){
                $tmp_int += $l2->val;
                $l2       = $l2->next;
            }
            $tmp_int += $carry;
            $node     = new ListNode();
            $node->val= $tmp_int%10;
            $carry    = floor($tmp_int/10);
            $tmp_int  = 0;
            $end->next= $node;                             
            $end = $node;
        }
        return $head->next;
    }
}