链表求和。
要求：不修改原始链表。
题目：
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7
这道题是 LeetCode2. Add Two Numbers的升级版，LeetCode2中，链表头是最低位，所以可以随着遍历两个链表，随着依次从最低位加起。但这道题链表头是MSB。
思路：
任意两数相加，需从最低位加起。但是由于链表只能从前往后遍历，也就是从最高位开始遍历。
所以可以用栈先进后出的特性，从前往后遍历，把最高位压入栈底。
1）定义两个栈，遍历两个链表，分别把1l, l2每一位压入栈里。
2）定义两个变量，sum 保存两位相加的和。res结点，它的值是sum取余。
3）进入循环，当栈s1, s2 有元素时，弹出栈顶元素，加到sum上。修改res的值 res.val = sum%10，新建一个carry结点保存进位，ListNode carry = new ListNode(sum/10) 。
将carry结点指向res: carry.next = res。将res向前移动，res = carry。更新sum的值：sum = sum / 10。
4）结束循环（s1, s2都为空）如果此时res.val为0，则返回res.next。如果res.val为1, 则返回res.
代码：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Stack<ListNode> s1 = new Stack<>(); Stack<ListNode> s2 = new Stack<>(); while(l1 != null) { s1.push(l1); l1 = l1.next; } while(l2 != null) { s2.push(l2); l2 = l2.next; } int sum = 0; ListNode res = new ListNode(0); while(!s1.isEmpty() || !s2.isEmpty()) { if(!s1.isEmpty()){ sum += s1.pop().val; } if(!s2.isEmpty()){ sum += s2.pop().val; } res.val = sum % 10; ListNode carry = new ListNode(sum / 10); carry.next = res; res = carry; sum = sum / 10; } return res.val == 0 ? res.next : res; } }
LeetCode445-Add Two Numbers II-Medium
原文：https://www.cnblogs.com/Jessiezyr/p/12990638.html