算法通关村第2关 | 链表加法问题解析
LeetCode369.用一个非空单链表来表示一个非负整数,然后将这个整数加一。计算是从低位开始的,而链表是从高位开始的,所以要处理就必须反转过来,此时可以使用栈,也可以使用链表反转来实现。基于栈实现的思路不算复杂,先把题目给出的链表遍历放到栈中,然后从栈中弹出栈顶数字 digit,加的时候再考虑一下进位的情况就ok了,加完之后根据是否大于0决定视为下一次要进位。
·
算法通关村第2关 | 链表加法问题解析
单链表加1
LeetCode369.用一个非空单链表来表示一个非负整数,然后将这个整数加一。
示例:
输入: [1,2,3]
输出: [1,2,4]
计算是从低位开始的,而链表是从高位开始的,所以要处理就必须反转过来,此时可以使用栈,也可以使用链表反转来实现。
基于栈实现的思路不算复杂,先把题目给出的链表遍历放到栈中,然后从栈中弹出栈顶数字 digit,加的时候再考虑一下进位的情况就ok了,加完之后根据是否大于0决定视为下一次要进位 。
public ListNode plusOne(ListNode head) {
Stack<Integer> st = new Stack();
while (head != null) {
st.push(head.val);
head = head.next;
}
int carry = 0;
ListNode dummy = new ListNode(0);
int adder = 1;
while (!st.empty() || carry > 0) {
int digit = st.empty() ? 0 : st.pop();
int sum = digit + adder + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
ListNode cur = new ListNode(sum);
cur.next = dummy.next;
dummy.next = cur;
adder = 0;
}
return dummy.next;
}
链表加法
LeetCode445题,给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外,这两个数字都不会以零开头。示例:
示例:
输入:(6 -> 1 -> 7) + (2 -> 9 -> 5),即617 + 295
输出:9 -> 1 -> 2,即912
使用栈实现
思路是先将两个链表的元素分别压栈,然后再一起出栈,将两个结果分别计算。之后对计算结果取模,模数保存到新的链表中,进位保存到下一轮。完成之后再进行一次反转就行了。
public static ListNode addInListByStack(ListNode head1, ListNode head2) {
Stack<ListNode> st1 = new Stack<ListNode>();
Stack<ListNode> st2 = new Stack<ListNode>();
while (head1 != null) {
st1.push(head1);
head1 = head1.next;
}
while (head2 != null) {
st2.push(head2);
head2 = head2.next;
}
ListNode newHead = new ListNode(-1);
int carry = 0;
//这里设置carry!=0,是因为当st1,st2都遍历完时,如果carry=0,就不需要进入循环了
while (!st1.empty() || !st2.empty() || carry != 0) {
ListNode a = new ListNode(0);
ListNode b = new ListNode(0);
if (!st1.empty()) {
a = st1.pop();
}
if (!st2.empty()) {
b = st2.pop();
}
//每次的和应该是对应位相加再加上进位
int get_sum = a.val + b.val + carry;
//对累加的结果取余
int ans = get_sum % 10;
//如果大于0,就进位
carry = get_sum / 10;
ListNode cur = new ListNode(ans);
cur.next = newHead.next;
//每次把最新得到的节点更新到neHead.next中
newHead.next = cur;
}
return newHead.next;
}
使用链表反转实现
先将两个链表分别反转,最后计算完之后再将结果反转
public class Solution {
public ListNode addInList (ListNode head1, ListNode head2) {
head1 = reverse(head1);
head2 = reverse(head2);
ListNode head = new ListNode(-1);
ListNode cur = head;
int carry = 0;
while(head1 != null || head2 != null) {
int val = carry;
if (head1 != null) {
val += head1.val;
head1 = head1.next;
}
if (head2 != null) {
val += head2.val;
head2 = head2.next;
}
cur.next = new ListNode(val % 10);
carry = val / 10;
cur = cur.next;
}
if (carry > 0) {
cur.next = new ListNode(carry);
}
return reverse(head.next);
}
private ListNode reverse(ListNode head) {
ListNode cur = head;
ListNode pre = null;
while(cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
更多推荐
已为社区贡献1条内容
所有评论(0)