Add Two Numbers这个问题的意思是，提供两条链表，每条链表表示一个十进制整数，其每一位对应链表的一个结点。比如345表示为链表5->4->3。而我们需要做的就是将两条链表代表的整数加起来，并创建一个新的链表并返回，新链表代表加总值。
这个问题与算法无关，其主要是操作链表这一数据结构，以及两个大数的加法。由于没有规定链表的长度，这意味着链表代表的整数可以任意大，这样就不能先利用链表计算出对应的整数值，之后利用加总值重新生成链表。我们必须手动处理两个大数的加法。
要谨慎两个个位数的加总结果是有可能需要进位的，即7+8实际上等于10x1+5，其中1应该进位到下一个结点，而5当作这个当前结点的值。
addTwoNumbers(Node n1, Node n2)
res = Node{val = (n1.val + n2.val) % 10, next = null}
tail = res
adv = (n1.val + n2.val) / 10
n1 = n1.next
n2 = n2.next
while n1 != null && n2 != null then
sum = n1.val + n2.val + adv
tail.next = Node{val = sum % 10, next = null}
tail = tail.next
adv = sum / 10
n1 = n1.next
n2 = n2.next
Node notEndedNode = (n1 == null ? n2 : n1)
while notEndedNode != null then
sum = notEndedNode .val + adv
tail.next = Node{val = sum % 10, next = null}
tail = tail.next
adv = sum / 10
notEndedNode = notEndedNode.next
while adv != 0 then
tail.next = Node{val = adv % 10, next = null}
tail = tail.next
adv = adv / 10
return res
下面直接给出java的实现代码
package cn.dalt.leetcode;
/**
* Created by Administrator on 2017/6/4.
*/
public class AddTwoNumbers {
public static void main(String[] args)
{
System.out.println(new AddTwoNumbers().addTwoNumbers(new ListNode(342), new ListNode(465)));
}
static class ListNode {
ListNode(int x)
{
val = x % 10;
int adv = x / 10;
if(adv != 0)
{
next = new ListNode(adv);
}
}
@Override
public String toString() {
return "" + val + (next != null ? "->" + next.toString() : "");
}
int val;
ListNode next;
}
static class NodeList{
ListNode tail;
ListNode root;
int advance = 0;
public NodeList(int x)
{
root = new ListNode(x % 10);
tail = root;
advance = x / 10;
}
public void append(int x)
{
x += advance;
ListNode temp = new ListNode(x % 10);
advance = x / 10;
tail.next = temp;
tail = temp;
}
public ListNode getResult()
{
while(advance != 0)
{
append(0);
}
return root;
}
@Override
public String toString() {
return root.toString();
}
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
NodeList list = new NodeList(l1.val + l2.val);
l1 = l1.next;
l2 = l2.next;
while(l1 != null && l2 != null)
{
list.append(l1.val + l2.val);
l1 = l1.next;
l2 = l2.next;
}
while(l1 != null)
{
list.append(l1.val);
l1 = l1.next;
}
while(l2 != null)
{
list.append(l2.val);
l2 = l2.next;
}
return list.getResult();
}
}