两个链表生成相加链表--牛客网算法题

两个链表生成相加链表

题目：
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
示例1
输入
复制
[9,3,7],[6,3]
返回值
复制
{1,0,0,0}

说下我的思路：
1.相加因为有可能进位，所以是从后向前加，但是链表是单向链表，这时我们会想起栈这个数据结构。
2.把两个链表的值分别压入栈中再相加不就是从后向前加了吗。但是还要考虑进位的问题。
3.我是通过和10比较分别进入两段逻辑，比10小的直接添加节点就行了，比10大的就要减10，对下一个数字加1.然后把减过的数生成节点添加到链表。
下面把代码贴出来：
public static ListNode addInList (ListNode head1, ListNode head2) {
// write code here
Stack stack1 = new Stack<>();
Stack stack2 = new Stack<>();

while(head1 != null){
stack1.push(head1.val);
head1 = head1.next;
}
while(head2 != null){
stack2.push(head2.val);
head2 = head2.next;
}
Integer result = 0;
Integer s1 = 0;
Integer s2 = 0;
ListNode n1 = new ListNode(0);
ListNode head = new ListNode(0);
while(!stack1.isEmpty() || !stack2.isEmpty()){
if(!stack1.isEmpty()){
s1 = stack1.pop();
}else{
s1 = 0;
}
if(!stack2.isEmpty()){
s2 = stack2.pop();
}else{
s2 = 0;
}
result = s1 + s2;
ListNode temp = new ListNode(0);
if(result < 10){
temp.val = result;
temp.next = n1;
n1 = temp;
}else{
Integer res = result - 10;
Integer sta = 0;
if(stack1.size() >= 1){
sta = stack1.pop();
sta += 1;
}else{
sta = 1;
}
stack1.push(sta);
temp.val = res;
temp.next = n1;
if(head == null){
head = n1;
}
n1 = temp;
}
}
ListNode frist = n1;
while (frist.next.next != null){
frist = frist.next;
}
frist.next = null;
return n1;
}

总结：
这次用的栈做的，其实也可以用其他数据结构，在做这样类型的算法题时，多考虑用数据结构的思路就会很容易做出来。

最后

以上就是义气白云为你收集整理的两个链表生成相加链表--牛客网算法题的全部内容，希望文章能够帮你解决两个链表生成相加链表--牛客网算法题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。