网站设计专业知识技能,网页设计实验报告需求分析,五十家装修公司官网,仿 wordpress主题题目类型 链表反转、栈 题目描述 * 题目#xff1a;
* 给你两个非空链表来表示两个非负整数#xff0c;数字最高位位于链表的开始位置。
* 它们的每个节点都只存储一个数字。将这两个数相加会返回一个新的链表。
* 你可以假设除了数字0外#xff0c;这两个数字都不会以0开头…题目类型 链表反转、栈 题目描述 * 题目
* 给你两个非空链表来表示两个非负整数数字最高位位于链表的开始位置。
* 它们的每个节点都只存储一个数字。将这两个数相加会返回一个新的链表。
* 你可以假设除了数字0外这两个数字都不会以0开头 示例 输入6 -- 1 --7 和 2 -- 9 --5 输出 9 -- 1 -- 2 实现方式 栈 反转链表 栈实现
思路 先将两个链表的元素分别压栈然后再一起出栈将两个结果分别计算。之后对计算的结果取模模数保存到新的链表中进位保存到下一轮完成之后再进行一次反转就行了 事项 我们知道在链表插入有头插法和尾插法两种。头插法就是每次都将新的结点插到head之前。而尾插法就是将新结点都插入到链表的表尾。两者的区别是尾插法的顺序与原始链表是一致的而头插法与原始链表是逆序的所以上面最后步如果不想进行反转可以将新结点以头插法 代码实现 /*** 使用栈实现两数相加* param head1 第一个链表头节点* param head2 第二个链表头节点* return 相加后的到的链表头节点*/public Node andTwoSingleListByStack(Node head1 , Node head2){StackNode stack1 new Stack();StackNode 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;}
