Emove

  • 首页
  • 归档
  • 分类
  • 标签

  • 搜索
context 反射 channel LRU BeanDefinition JVM 装饰者模式 MyBatis 快慢指针 归并排序 链表 hash表 栈 回溯 贪心 主从复制 二分查找 双指针 动态规划 AOF RDB 规范 BASE理论 CAP B树 RocketMQ Sentinel Ribbon Eureka 命令模式 访问者模式 迭代器模式 中介者模式 备忘录模式 解释器模式 状态模式 策略模式 职责链模式 模板方法模式 代理模式 享元模式 桥接模式 外观模式 组合模式 适配器模式 建造者模式 原型模式 工场模式 单例 UML 锁 事务 sql 索引

两数之和

发表于 2020-03-29 | 分类于 算法题 | 18 | 阅读次数 128

题目:给定两个表示非负整数的非空链表。链表中的数字以相反的顺序存储,并且每个节点都包含一个数字。将两个链表的数字相加,并将求得的和以链表的形式返回。

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

题解:

  1. 链表中数字以反序存储

  2. 两个链表相加存在两种可能

    1. 两个链表长度相等
    2. 其中一个链表长度大于另外一个链表
  3. 若两个链表长度相等,且两个链表的最高位相加之和大于10,即有进位,应为其创建新的节点。

    例如: 50 + 61,其中最高位相加之和为11,即进位为1,返回的链表应为 1 -> 1 -> 1

题解代码如下:

/**
 * 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) {
        ListNode pre = new ListNode(0);
        // 头结点
        ListNode head = pre;
        int carry = 0;
        // 存在三种情况,l1的长度等于l2的长度,或者一长一短,还有最后节点遍历完之后,还存在值应为其创建节点
        while (l1 != null || l2 != null || carry != 0) {
            ListNode cur = new ListNode(0);
            int sum = ((l1 == null) ? 0 : l1.val) + ((l2 == null) ? 0 : l2.val) + carry;
            cur.val = sum % 10;
            carry = sum / 10;
            pre.next = cur;
            pre = cur;

            l1 = (l1 == null) ? l1 : l1.next;
            l2 = (l2 == null) ? l2 : l2.next;
        }
        return head.next;
    }
}
# context # 反射 # channel # LRU # BeanDefinition # JVM # 装饰者模式 # MyBatis # 快慢指针 # 归并排序 # 链表 # hash表 # 栈 # 回溯 # 贪心 # 主从复制 # 二分查找 # 双指针 # 动态规划 # AOF # RDB # 规范 # BASE理论 # CAP # B树 # RocketMQ # Sentinel # Ribbon # Eureka # 命令模式 # 访问者模式 # 迭代器模式 # 中介者模式 # 备忘录模式 # 解释器模式 # 状态模式 # 策略模式 # 职责链模式 # 模板方法模式 # 代理模式 # 享元模式 # 桥接模式 # 外观模式 # 组合模式 # 适配器模式 # 建造者模式 # 原型模式 # 工场模式 # 单例 # UML # 锁 # 事务 # sql # 索引
最长子串
索引
  • 文章目录
  •   |  
  • 概览
林亦庭

林亦庭

less can be more

87 文章
11 分类
54 标签
RSS
Github
Creative Commons
© 2021 林亦庭
粤ICP备20029050号