牛客网高频算法题系列-BM11-链表相加(二)
题目形容
假如链表中每一个节点的值都在 0 - 9 之间，那么链表整体就能够代表一个整数。给定两个这种链表，请生成代表两个整数相加值的后果链表。
原题目见：BM11 链表相加(二)
解法一：应用栈
首先，非凡状况判断：
- 如果链表一为空，则间接返回链表二
- 如果链表二为空，则间接返回链表一
否则，应用2个栈用来寄存两个链表的结点：
- 首先将两个链表中的结点增加到栈中；
- 遍历2个栈，即执行加法，将值增加到新的栈中这样能够按倒序进行结点值相加，其中须要应用一个变量记录进位值；
- 须要留神的是，遍历完结后，须要依据进位值判断是否须要增加额定的结点；
- 最初，依据新的栈结构相加后的链表并返回之。
如果不想应用多余的栈空间，能够思考先将两个链表倒序排列后，再执行加法。
代码
import java.util.Stack;public class Bm011 { /** * 链表相加：应用栈 * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ public static ListNode addInList(ListNode head1, ListNode head2) { // 如果链表一为空，则间接返回链表二 if (head1 == null) { return head2; } // 如果链表二为空，则间接返回链表一 if (head2 == null) { return head1; } // 2个栈用来寄存两个链表的结点 Stack<ListNode> nodes1 = new Stack<>(); Stack<ListNode> nodes2 = new Stack<>(); while (head1 != null) { nodes1.push(head1); head1 = head1.next; } while (head2 != null) { nodes2.push(head2); head2 = head2.next; } // 记录进位值 int addOne = 0; Stack<Integer> newNodes = new Stack<>(); // 遍历栈，即执行加法，将值增加到新的栈中 while (!nodes1.isEmpty() || !nodes2.isEmpty()) { int val1 = 0, val2 = 0, newVal = 0; if (!nodes1.isEmpty()) { val1 += nodes1.pop().val; } if (!nodes2.isEmpty()) { val2 += nodes2.pop().val; } newVal += addOne + val1 + val2; if (newVal > 9) { newVal = newVal % 10; addOne = 1; } else { addOne = 0; } newNodes.push(newVal); } if (addOne == 1) { newNodes.push(1); } ListNode newHead = new ListNode(-1); ListNode next = newHead; while (!newNodes.isEmpty()) { next.next = new ListNode(newNodes.pop()); next = next.next; } return newHead.next; } public static void main(String[] args) { // 链表一： 1 -> 3 -> 5 ListNode head1 = ListNode.testCase3(); // 链表二： 2 -> 4 -> 6 ListNode head2 = ListNode.testCase4(); // 测试用例，冀望输入： 3 -> 8 -> 1 ListNode.print(addInList(head1, head2)); }}$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量！