题目:给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
思路:
题目中给出两个非空链表,求非空链表的和,有两个注意点,一个是进位,另一个是逆序。
首先会想到一个方法,先将链表逆序转成数字,然后数字相加,然后数字转成链表逆序。
缺陷就是如果链表过长,就有可能导致int/long溢出。
第二个方法就是使用双指针。分别在两个链表头部开始,使用一个进位变量进行链表位置的记录,然后如果第一个链表不为空
进行++ ,第二个链表不为空继续++,加完之后将得出的结果放到新开辟的链表中,注意此时放入的是数字的取模之后的值。
9=9,10的话就是0.
然后进行链表移动。
然后将t重置,t=t/10,如果之前t<10,那么t=0,如果t>10...
最后输出链表即可。
/** * 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 demo=new ListNode(-1),pre=demo; int t=0; while(l1!=null||l2!=null||t!=0){ if(l1!=null){ t+=l1.val; l1=l1.next; } if(l2!=null){ t+=l2.val; l2=l2.next; } pre.next=new ListNode(t%10); pre=pre.next; t=t/10; } return demo.next; } }