题解 | #链表相加(二)#
链表相加(二)
http://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b
具体做法：
申请两个栈空间和一个标记位，然后将两个栈中内容依次相加，将结果倒插入新节点中。
申请两个栈空间和一个标记位，然后将两个栈中内容依次相加，将结果倒插入新节点中。
具体过程如下图：
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
LinkedList<Integer> list1 = new LinkedList<>(); //list1栈
LinkedList<Integer> list2 = new LinkedList<>(); //list2栈
putData(list1, head1); //入栈
putData(list2, head2);
ListNode newNode = null;
ListNode head = null;
int carry = 0; //标记进位
while (!list1.isEmpty() || ! list2.isEmpty() || carry != 0) {
int x = (list1.isEmpty()) ? 0 : list1.pop(); //依次从栈中取出
int y = (list2.isEmpty()) ? 0 : list2.pop();
int sum = x + y + carry; //与进位一起相加
carry = sum / 10; //更新进位
//将计算值放入节点
newNode = new ListNode(sum % 10);
//更新下一个节点的指向
newNode.next = head;
head = newNode;
}
return head;
}
private void putData(LinkedList<Integer> s1, ListNode head1) {
if (s1 == null) s1 = new LinkedList<>();
//遍历节点将其插入栈中
while (head1 != null) {
s1.push(head1.val);
head1 = head1.next;
}
}
}
