转载

LeetCode:两数相加

原文链接:https://blog.csdn.net/weixin_43724845/

刷题神器:LeetCode官方网站

一、题目还原

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

二、解题思路

① Edge Case:如果两个链表都为空,直接返回null
② 定义一个进位数表示每次相加结果进了多少位
③ 遍历两个链表,只要任意一个链表存在next,或进位数不等于0都需要进行遍历
④ 返回链表中进行判断记录,如果总和大于10,则记录余数,反之记录总和

三、代码展示

① main函数

public static void main(String[] args) {
	ListNode l1 = new ListNode(2);
	l1.next = new ListNode(4);
	l1.next.next = new ListNode(9);
	
	ListNode l2 = new ListNode(5);
	l2.next = new ListNode(6);
	l2.next.next = new ListNode(4);

	addTwoNumbers(l1,l2);
}

② ListNode类

public static class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}

③ addTwoNumbers方法函数

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if(l1 == null && l2 == null){
        return null;
    }

    //进位数
    int flag = 0;
    ListNode returnNode = new ListNode(0);
    ListNode tempNode = returnNode;

    //为了方便输出查看定义下标
    int inedx = 0;
    while(null != l1 || null != l2 || flag != 0){
        int value1 = 0;
        int value2 = 0;

        if(null != l1){
            value1 = l1.val;
            l1 = l1.next;
        }else{
            value1 = 0;
        }

        if(null != l2){
            value2 = l2.val;
            l2 = l2.next;
        }else{
            value2 = 0;
        }

        if((value1+value2+flag) / 10 > 0 ){
            tempNode.next = new ListNode((value1+value2+flag) % 10);
        }else{
            tempNode.next = new ListNode(value1+value2+flag);
        }

        flag = (value1+value2+flag) / 10;

        tempNode = tempNode.next;

        System.out.println(inedx++ + ":"+tempNode.val);

    }
    return returnNode.next ;
}

控制台输出:

0:7
1:0
2:4
3:1

Process finished with exit code 0

四、自我总结

这是LeetCode题库中的第二题,难度为中等,思路比较简单,博主卡在了ListNode的遍历上,刚写完的时候是这样的

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if(l1 == null && l2 == null){
        return null;
    }

    //进位数
    int flag = 0;
    ListNode returnNode = new ListNode(0);

    int index = 0;
    while(null != l1 || null != l2 || flag != 0){
        int value1 = 0;
        int value2 = 0;

        if(null != l1){
            value1 = l1.val;
            l1 = l1.next;
        }else{
            value1 = 0;
        }

        if(null != l2){
            value2 = l2.val;
            l2 = l2.next;
        }else{
            value2 = 0;
        }

        if((value1+value2+flag) / 10 > 0 ){
            returnNode = new ListNode((value1+value2+flag) % 10));
        }else{
            returnNode = new ListNode(value1+value2+flag);
        }
        flag = (value1+value2+flag) / 10;
        System.out.println(index+":returnNode.val == "+returnNode.val);
        returnNode = returnNode.next;
        index++;

    }
    
	System.out.println(returnNode);
    return returnNode ;
}

输出结果

0:returnNode.val == 7
1:returnNode.val == 0
2:returnNode.val == 4
3:returnNode.val == 1
null

Process finished with exit code 0

看到输出结果时非常纳闷,明明都输出正确了,为什么最后return还是null,经常反复查看终于返现问题出现在returnNode = returnNode.next;这一段上,其实我在遍历的时候并没有进行存储,而是把returnNode当成游标一样进行使用,最终无论结果如何,返回的都会是returnNode.next也就是null。知道问题原因后将代码进行调整,最终一次性提交成功,瞬间自信心爆棚!
Q2提交记录

正文到此结束
本文目录