【题目】
将链表组成的数相加
leetcode2变式，2题是高位在后，现在是高位在前节点
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [7,2,4,3], l2 = [5,6,4] Output: [7,8,0,7]
Example 2:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [8,0,7]
Example 3:
Input: l1 = [0], l2 = [0] Output: [0]
【思路】
链表反转，转换成leetcode2链表倒序相加即可
反转：https://www.cnblogs.com/inku/p/15211126.html
相加：https://www.cnblogs.com/inku/p/15210210.html
也可以用stack，不过耗时
【代码】
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { l1=reverse(l1); l2=reverse(l2); ListNode ans=new ListNode(); ListNode pans=ans; int cnt=0; while (l1!=null||l2!=null){ int sum=(l1==null?0:l1.val)+(l2==null?0:l2.val)+cnt; ans.next=new ListNode(sum%10); ans=ans.next; cnt=sum/10; if(l1!=null) l1=l1.next; if(l2!=null) l2=l2.next; } if(cnt>0) ans.next=new ListNode(cnt); return reverse(pans.next); } public ListNode reverse(ListNode l){ ListNode cur=l; ListNode next=l; ListNode pre=null; while(cur!=null){ next=cur.next; cur.next=pre; pre=cur; cur=next; } return pre; } }
用耗时的stack
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { Stack<Integer> s1=new Stack<>(); Stack<Integer> s2=new Stack<>(); Stack<Integer> s3=new Stack<>(); ListNode tmp=new ListNode(0); ListNode ans=tmp; while(l1!=null){ s1.push(l1.val); l1=l1.next; } while(l2!=null){ s2.push(l2.val); l2=l2.next; } int cnt=0; while (!s1.isEmpty()||!s2.isEmpty()){ if(s1.isEmpty()) s1.push(0); if(s2.isEmpty()) s2.push(0); int sum=s1.pop()+s2.pop()+cnt; cnt=sum/10; s3.push(sum%10); } if(cnt>0) s3.push(cnt); while (!s3.isEmpty()){ tmp.next=new ListNode(s3.pop()); tmp=tmp.next; } return ans.next; }