文档章节

给定两个用链表表示的整数,每个结点包含一个数位。这些数位是反向存放的,也就是个位排在链表首部

一贱书生
 一贱书生
发布于 2016/11/16 15:23
字数 447
阅读 19
收藏 0

 

      假设这些数位是正向存放的。

LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2, int carry)
{
/*两个链表全部都为空且进位为0,则函数返回*/
if (l1 == null &&l2 == null&&carry == 0)
{
return null;
}
LinkedListNode result = new LinkedListNode();
/*将value以及l1和l2的data相加*/
int value = carry;
if (l1 != null)
{
value += l1.data;
}
if (l2 != null)
{
value += l2.data;
}
result.data = value % 10;/*求和结果的个数*/
/*递归*/
LinkedListNode more = addLists(l1==null?null:l1.next,l2==null?null:l2.next,value>=10?1:0);
result.setNext(more);
return result;
}

      在实现这段代码时,务必注意处理一个链表比另一个链表结点少的情况。不然可能会出现指针异常。

发火进阶

public class PartialSum
{
public LinkedListNode sum=null;
public int carry=0;
}
    LinkedListNode addLists(LinkedListNode l1,LinkedListNode l2)
    {
    int len1=length(l1);
    int len2=length(l2);
    //用零填充较短的链表
    if(len1<len2)
    {
    l1=padList(l1,len2-len1);
    }
    else
    {
    l2=padList(l2,len1-len2);
    }
    //对两个链表求和
    PartialSum sum=addListsHelper(l1,l2);
    //如有进位,则插入链表首部,否则,直接返回整个链表
    if(sum.carry==0)
    {
    return sum.sum;
    }
    else
    {
    LinkedListNode result=insertBefore(sum.sum,sum.carry);
    return result;
    }
    }
    PartialSum addListsHelper(LinkedListNode l1,LinkedListNode l2)
    {
        if(l1==null && l2==null)
        {
        PartialSum sum=new PartialSum();
        return sum;
        }
        //对较小数字递归求和
        PartialSum sum=addListHelper(l1.next,l2.next);
        //将进位和当前数据相加
        int val=sum.carry +l1.data+l2.data;
        //插入当前数字的求和结果
        LinkedListNode full_result=insertBefore(sum.sum,val%10);
        //返回求和结果和进位值
        sum.sum=full_result;
        sum.carry=val/10;
        return sum;
    }
    //用零填充链表
    LinkedListNode padList(LinkedListNode l,int padding)
    {
    LinkedListNode head=l;
    for(int i=0;i<padding;i++)
    {
    LinkedListNode n=new LinkedListNode(0,null,null);
    head.prev=n;
    n.next=head;
    head=n;
    }
    return head;
    }
   
     //辅助函数,将结点插入链表首部
    LinkedListNode insertBefore(LinkedListNode list,int data)
    {
    LinkedListNode node=new LinkedListNode(data,null,null);
    if(list!=null)
    {
    list.prev=node;
    node.next=list;
    }
    return node;
    }

© 著作权归作者所有

一贱书生
粉丝 20
博文 724
码字总数 600123
作品 0
私信 提问
单链表表示的两个数相加

原题   You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the tw......

一贱书生
2016/12/06
20
0
[算法总结] 一文搞懂面试链表题

本文首发于我的个人博客:尾尾部落 链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。 1. 在 O(1) 时间删除链表节点 题目描述:给定单向链表的...

繁著
2018/08/28
0
0
玩转算法面试:(五)LeetCode链表类问题

在链表中穿针引线 链表和数组都是线性结构,但是链表和数组的不同在于数组可以随机的对于数据进行访问。给出索引。可以以O(1)的时间复杂度迅速访问到该元素。 链表只能从头指针开始。 next指...

天涯明月笙
2017/09/22
0
0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
CodingInterview 一刷

1. 找出数组中重复的数字 题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一...

BookThief
2018/08/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

状态模式

//相当把一个State对象存到Context对象中,然后通过Context实例化对象调用保存的state对象去调用state的相应的方法 https://blog.csdn.net/syc434432458/article/details/51210361...

南桥北木
30分钟前
3
0
基于 Jenkins + JaCoCo 实现功能测试代码覆盖率统计

本文首发于:Jenkins 中文社区 使用 JaCoCo 统计功能测试代码覆盖率? 对于 JaCoCo,有所了解但又不是很熟悉。 "有所了解"指的是在 CI 实践中已经使用 JaCoCo 对单元测试代码覆盖率统计: 当...

Jenkins中文社区
38分钟前
4
0
聊聊Elasticsearch的OsProbe

序 本文主要研究一下Elasticsearch的OsProbe OsProbe elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/monitor/os/OsProbe.java public class OsProbe { private static f......

go4it
38分钟前
2
0
谈谈lucene的DocValues特性之NumericDocValuesField

在默认实现的DocValuesCosumer中,数值有可能分块存储也有可能放在一个数据块中存储。 分块的大小默认是16384,并且通过预先计算如果按一个块存储最大值与最小值的差所占用的比特数和分块存储...

FAT_mt
56分钟前
2
0
【BATJ】面试必问MySQL索引实现原理

BATJ面试题剖析 1、为什么需要使用索引? 2、数据结构Hash、平衡二叉树、B树、B+树区别? 3、机械硬盘、固态硬盘区别? 4、Myisam与Innodb B+树的区别? 5、MySQL中的索引什么数据结构? 6、...

须臾之余
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部