思路:
取出链表对应结点的值, 相加结果存到新链表对应的结点, 由于每个结点只存一位数, 而相加结果有可能是两位, 因此需要进位, 每次相加时将进位加入计算.
具体如下:
创建两个结点用来分别遍历两个链表, 都指向对应链表的首结点.
1) 遍历两链表, 直到两链表都为空:
a: 取出两链表的值与进位 carry 相加为 sum, 该值可能大于 10, 因此用 carry 保存每次相加的结果的进位进位值 carry=sum/10,
b: 将 sum 的个位 (sum%10) 存入新链表中下一个结点 (这样, 提前创建了新的结点, 新链表前移时就不会报空指针异常)
c: 用于遍历的两个结点前进一步.
d: 新链表也前进一步.
2) 最后, 遍历结束, 判断 carry 是否为 0, 若不为 0, 则将 carry 的值存入新链表的下一个结点.
参考代码:
- public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
- ListNode cur1=l1;
- ListNode cur2=l2;
- ListNode result=new ListNode(0);
- ListNode cur=result;
- int carry=0;
- int x=0;
- int y=0;
- int sum=0;
- while(cur1!=null||cur2!=null){
- if(cur1!=null){
- x=cur1.val;
- }else{
- x=0;
- }
- if(cur2!=null){
- y=cur2.val;
- }else{
- y=0;
- }
- sum=x+y+carry;
- carry=sum/10;
- cur.next=new ListNode(sum%10);
- cur=cur.next;
- if(cur1!=null){
- cur1=cur1.next;
- }
- if(cur2!=null){
- cur2=cur2.next;
- }
- }
- if(carry!=0){
- cur.next=new ListNode(carry);
- }
- return result.next;
- }
两数相加
来源: http://www.bubuko.com/infodetail-3086539.html