leetcode 2. 两数相加

对PHPer来说考察的是对象复制、链表尾插、大数加法这三个知识点的掌握情况。

题干

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

 

示例

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

 

实现

php

执行用时:16 ms, 在所有 PHP 提交中击败了95.28%的用户
内存消耗:14.8 MB, 在所有 PHP 提交中击败了100.00%的用户

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        $flag=0; //进位
        $first=0;//第一位的结果

        //先计算第一位结果,判断是否有产生进位
        $first=$l1->val+$l2->val;
        if($first>=10){
            $flag=1;
            $first-=10;
        }

        //用计算出来的 first 第一位结果先初始化链表
        $newList=new ListNode($first);
        $newListCopy=$newList;
        
        while($l1->next != null && $l2->next != null){
            //两个链表都未非空
            $l1=$l1->next;
            $l2=$l2->next;

            $current=$l1->val+$l2->val+$flag;//当前计算位
            if($current>=10){
                //大等于10  需要进位
                $flag=1;
                $current-=10;
            }else{
                //小等于10  不需要进位
                $flag=0;
            }

            //插入链表尾部
            $newListNode=new ListNode($current);
            $newListCopy->next=$newListNode;
            $newListCopy=$newListNode;
        }
        
        while($l1->next != null){
            //l1链表非空
            $l1=$l1->next;

            $current=$l1->val+$flag;//当前计算位
            if($current>=10){
                //大等于10  需要进位
                $flag=1;
                $current-=10;
            }else{
                //小等于10  不需要进位
                $flag=0;
            }

            //插入链表尾部
            $newListNode=new ListNode($current);
            $newListCopy->next=$newListNode;
            $newListCopy=$newListNode;
        }

        while($l2->next != null){
            //l2链表非空
            $l2=$l2->next;

            $current=$l2->val+$flag;//当前计算位
            if($current>=10){
                //大等于10  需要进位
                $flag=1;
                $current-=10;
            }else{
                //小等于10  不需要进位
                $flag=0;
            }

            //插入链表尾部
            $newListNode=new ListNode($current);
            $newListCopy->next=$newListNode;
            $newListCopy=$newListNode;
        }

        if($flag!=0){
            //将进位插入链表尾部
            $newListNode=new ListNode($flag);
            $newListCopy->next=$newListNode;
            $newListCopy=$newListNode;

            //清空进位
            $flag=0;
        }

        return $newList;
    }
}

 

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇