LeetCode 题解与知识点 2. 两数相加 Add-Two-Numbers

码农天地 - 2020-10-26 09:34:15

---

题目链接

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

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。

更多关于php的阅读

Tags 标签

leetcodephp链表

扩展阅读