Finder 机器学习 主从复制 Java中高进阶架构 macos enums ant signalr tinymce Normalizecss Validator Plupload Animsition vue的钩子函数 jquery绑定事件的方法 matlab根号怎么打出来 移动端上传图片插件 vue与html5 python逻辑运算符 python中文手册 python中的for循环 python中time python中文教程 python获取输入 java连接mysql java中的基本数据类型 java课程 java定义变量 javalist数组 linux镜像安装 微信签名一句话至自己 1660ti 淘宝自动发货软件 dll下载 medcalc mysql时间比较 编程电子书 冰冠堡垒单刷路线 jdk9 c4dr20
当前位置: 首页 > 学习教程  > 编程语言

【刷题1】LeetCode 2. 两数相加 java题解

2020/11/24 9:21:00 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目 https://leetcode-cn.com/problems/add-two-numbers/ 我的暴躁解法 我太垃圾了,写了一小时,各种Bug 代码 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val…

题目

https://leetcode-cn.com/problems/add-two-numbers/
在这里插入图片描述

我的暴躁解法

我太垃圾了,写了一小时,各种Bug

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
		//我们要在l1链表上做修改
        ListNode head=l1;//保存头结点
        int tmp=0;//进位

        while(l1!=null&&l2!=null){
            l1.val=l1.val+l2.val+tmp;
            tmp=l1.val/10;
            l1.val=l1.val%10;
            //第二个链表比较长,此时第一个链表已经是最后一个节点了
            if(l1.next==null&&l2.next!=null){
                //l1不动,l2是下一个值
                l2=l2.next;
                break;
            }
            //一样长,都到了最后一个结点,可以返回了
            if(l1.next==null&&l2.next==null){
            	//有进位,需要再创建一个节点
                if(tmp!=0){
                    l1.next=new ListNode(tmp);
                }
                return head;               
            }
            l1=l1.next;
            l2=l2.next;
        }


        //链表2长
        if(l2!=null){
            while(l2!=null){
                int val=l2.val+tmp;//和
                tmp=val/10;//下一个进位
                l1.next=new ListNode(val%10);//放到l1的后一个
                //这是最后一个l2节点,可以返回了
                if(l2.next==null){
                	//有进位,创建一个节点
                    if(tmp!=0){
                        l1.next.next=new ListNode(tmp);
                        return head;
                    }                    
                }
                l1=l1.next;
                l2=l2.next;
            }
        }

        //链表1长
        if(l1!=null){
            while(l1!=null){
                l1.val=l1.val+tmp;
                tmp=l1.val/10;
                l1.val=l1.val%10;
                //这是最后一个l1节点。可以返回了
                if(l1.next==null){
                	//有进位,创建一个节点
                    if(tmp!=0){
                        l1.next=new ListNode(tmp);
                        return head;
                    }                    
                }
                l1=l1.next;
            }
        }
        return head;
    }
}

复杂度

时间复杂度:O(max(m,n)),其中m,n 为两个链表的长度。我们要遍历两个链表的全部位置,而处理每个位置只需要 O(1)的时间。
空间复杂度:O(max(m,n))。答案链表的长度最多为较长链表的长度+1。

结果

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_400022.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?