算法通关村第二关——链表加法的问题解析

题目类型

链表反转、栈

题目描述

* 题目：
* 给你两个非空链表来表示两个非负整数，数字最高位位于链表的开始位置。
* 它们的每个节点都只存储一个数字。将这两个数相加会返回一个新的链表。
* 你可以假设除了数字0外，这两个数字都不会以0开头

示例

输入：6 --> 1 -->7    和   2 --> 9 -->5

输出： 9 --> 1 --> 2

实现方式

栈

反转链表

栈实现 

思路

        先将两个链表的元素分别压栈，然后再一起出栈，将两个结果分别计算。之后对计算的结果取模，模数保存到新的链表中，进位保存到下一轮，完成之后再进行一次反转就行了

事项

我们知道在链表插入有头插法和尾插法两种。头插法就是每次都将新的结点插到head之前。而尾插法就是将新结点都插入到链表的表尾。两者的区别是尾插法的顺序与原始链表是一致的，而头插法与原始链表是逆序的，所以上面最后步如果不想进行反转，可以将新结点以头插法 

代码实现 

    /***  使用栈实现两数相加* @param head1 第一个链表头节点* @param head2 第二个链表头节点* @return 相加后的到的链表头节点*/public Node andTwoSingleListByStack(Node head1 , Node head2){Stack<Node> stack1 = new Stack<>();Stack<Node> stack2 = new Stack<>();//  将链表节点数据入栈while (head1 != null){stack1.push(head1);head1 = head1.next;}while (head2 != null){stack2.push(head2);head2 = head2.next;}// 构造虚拟节点Node dummyNode = new Node(0);// carry 用于标识是否有进位int carry = 0;while (!stack1.empty() || !stack2.empty() || carry != 0){// 使用两个链表来存储栈中的数据Node a = new Node(0);Node b = new Node(0);if (!stack1.empty()){a = stack1.pop();}if (! stack2.empty()){b = stack2.pop();}int sum = a.data + b.data + carry;int ans = sum % 10;carry = sum / 10;Node cur = new Node(ans);cur.next = dummyNode.next;dummyNode.next = cur;}return dummyNode.next;}

链表反转实现

思路

先将两个链表分别反转，最后计算完之后再将结果反转，一共有三次反转操作

代码实现

    public Node addTwoSingleListByReverseList(Node head1 , Node head2){// 反转链表，将低位放在表头，高位放在表尾head1 = reverseList(head1);head2 = reverseList(head2);// 定义虚拟节点Node dummyNode = new Node(0);Node cur = dummyNode;int carry = 0;while (head1 != null || head2 != null){int val = carry;if (head1 != null){val += head1.data;head1 = head1.next;}if (head2 != null){val += head2.data;head2 = head2.next;}int ans = val % 10;carry = val / 10;cur.next = new Node(ans);cur = cur.next;}if (carry > 0 ){cur.next = new Node(carry);}return reverseList(dummyNode.next);}private Node reverseList(Node head){Node pre = null;Node cur = head;while (cur != null){Node next = cur.next;// 发生关系cur.next = pre;pre = cur;cur = next;}return pre;}