题目链接

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