福建省建设注册执业管理中心网站,大型租车门户网站商业版源码,网站建设人员性格,岳阳网站开发报价用链表代表2个数字#xff0c;这2个数字相加的和用链表返回。 最高位在链表的head.
思路#xff1a;
1.链表逆序
数字相加是从低位到高位的#xff0c;然而链表中的数字是从高位指向低位。 所以涉及到链表的逆序。
逆序之后只需从head到tail把两个链表的数字相加#x…
用链表代表2个数字这2个数字相加的和用链表返回。 最高位在链表的head.
思路
1.链表逆序
数字相加是从低位到高位的然而链表中的数字是从高位指向低位。 所以涉及到链表的逆序。
逆序之后只需从head到tail把两个链表的数字相加再用一个int表示进位。
链表的逆序: 最左边的数字逆序后应该是tail, 它的next指向null. 后面的数字每次都指向它的前一个数字。 所以用cur表示当前node, cur.next指向它前一个node, 然后cur移动到链表的下一节点不停地把cur.next指向前一个node.
在把结果的数字一个一个地保存进结果的链表中时 不断地把新数字指向前一个数字就实现了从低位到高位保存的效果。
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode newHead null;int carry 0;l1 reverseList(l1);l2 reverseList(l2);while(l1 ! null || l2 ! null || carry 0) {int num1 (l1 ! null ? l1.val : 0);int num2 (l2 ! null ? l2.val : 0);int sum num1 num2 carry;int num sum % 10;carry sum / 10;ListNode cur new ListNode(num);cur.next newHead;newHead cur;l1 (l1 ! null ? l1.next : null);l2 (l2 ! null ? l2.next : null);}return newHead;}ListNode reverseList(ListNode head) {ListNode pre null;ListNode cur head;while(cur ! null) {ListNode next cur.next;cur.next pre;pre cur;cur next;}return pre;}
}2.Stack
如果不想用链表逆序可以用Stack, 同样可以达到逆序的效果但是速度不及上面的快。 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {StackInteger st1 new Stack();StackInteger st2 new Stack();ListNode res null;int carry 0;//相当于逆序链表while(l1 ! null) {st1.push(l1.val);l1 l1.next;}while(l2 ! null) {st2.push(l2.val);l2 l2.next;}while(!st1.empty() || !st2.empty() || carry 0) {int num1 st1.empty() ? 0 : st1.pop();int num2 st2.empty() ? 0 : st2.pop();int sum num1 num2 carry;int num sum % 10;carry sum / 10;ListNode cur new ListNode(num);cur.next res;res cur;}return res;}
