LeetCode算法题2.两数相加

2020-02-13
阅读量 | 字数：771字 | 预计阅读时长：3分钟

题目

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

解题思路

1.确定解题方法
对两个链表对应位置的元素进行求和，然后将最终处理好的和元素item尾插法插入新链表的对应节点中，遍历过程中若两个链表不等长，那么只需要把仍然存在的链表的元素尾插法放进新链表即可。
2.提交前考虑到的问题
（1）两数相加，要注意进位，设置flag代表进位，初始化为0，如果flag为1，说明有进位，item需要加1，加1后置flag为0
（2）两数相加≥10的时候，flag置1，并且将item对10取余后的值存入链表
3.测试时踩过的坑
（1）新建的链表的时候需要有个值来初始化头结点，这个结点不出现在最后的结果链表中
（2）最后一对节点的和需要进位的时候，需要处理这单独的1，新建一个val值为1的结点，把它尾插到当前结果链表的最后
（3）最开始的坑，其实是解题方法不对，先遍历两个链表把数拼接起来，然后求和sum，再把sum的每一位尾插到新链表，这个方法的错误之处就在于不能解决很大的数据求和，超过int或者long的表示范围就很难受了。

代码

/**
 * 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) {
        int item = 0;
    	int flag = 0;
    	ListNode res = new ListNode(0);
        ListNode q = res;
    	while(l1 !=null || l2 != null){
    		if(l1 !=null && l2 !=null) {
    			item = l1.val + l2.val;
                l1 = l1.next;
                l2 = l2.next;
    		}
    		else if (l1 !=null && l2 ==null ) {
    			item = l1.val;
                l1 = l1.next;
    		}
    		else if (l1 ==null && l2 !=null ) {
    			item = l2.val;
                l2 = l2.next;
    		}
            
            if (flag == 1) {	// 判断是否有进位
            	item += 1;		// 有进位就+1
            	flag = 0;		// 进位标志符置为0
            }
            if (item >= 10) {	// 判断是否能产生进位
            	flag = 1;		// 能产生进位就置flag为1
            	item = item % 10;	// 只保留item的个位的数值
            }
            ListNode p = new ListNode(item);
            q.next = p;			// 尾插法
            q = q.next; 		// 让q始终指向的是结果链表res的尾部
        }
        // 已有元素求和完毕后，如果进位标志符仍然为1，说明和的位数增加了		
        // 一位，新链表的长度比原来的两个链表中的最长的一个还需要多一个	
        // 结点，且结点的val值为1。
    	if (flag == 1) {		
    		q.next = new ListNode(flag);
            q.next.next = null;
    	}
        return res.next;
    }
}

官方题解链接

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/7a0b06bd.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。