描述
假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。
给定两个这种链表,请生成代表两个整数相加值的结果链表。
数据范围:0≤𝑛,𝑚≤10000000≤n,m≤1000000,链表任意值 0≤𝑣𝑎𝑙≤90≤val≤9
要求:空间复杂度 𝑂(𝑛)O(n),时间复杂度 𝑂(𝑛)O(n)
例如:链表 1 为 9->3->7,链表 2 为 6->3,最后生成新的结果链表为 1->0->0->0。
示例1
输入:[9,3,7],[6,3]
返回值:{1,0,0,0}
说明:如题面解释
示例2
输入:[0],[6,3]
返回值:{6,3}
备注:
1≤𝑛,𝑚≤1061≤n,m≤106 0≤𝑎𝑖,𝑏𝑖≤90≤ai,bi≤9
三个栈。
package com.qcby;
import java.util.List;
import java.util.Stack;
public class BM11 {
public ListNode addInList(ListNode head1, ListNode head2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
ListNode cur = head1;
while (cur != null) {
stack1.push(cur.val);
cur = cur.next;
}
cur = head2;
while (cur != null) {
stack2.push(cur.val);
cur = cur.next;
}
Stack<Integer> stack3 = new Stack<>();
int res = 0;//记录相加之后的进位
while (!stack1.empty() || !stack2.empty()) {
int sum = res;
if (!stack1.empty()) sum += stack1.pop();
if (!stack2.empty()) sum += stack2.pop();
stack3.push(sum % 10);
res = sum / 10;
}
if (res > 0) stack3.push(res);
//生成新的链表
ListNode listnode = new ListNode(0);
ListNode dummy = listnode;
while (!stack3.empty()) {
listnode.next = new ListNode(stack3.pop());
listnode = listnode.next;
}
return dummy.next;
}
static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
}