LeetCode: Add Two Numbers
java是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台(即JavaEE, JavaME, JavaSE)的总称。本站提供基于Java框架struts,spring,hibernate等的桌面应用、web交互及移动终端的开发技巧与资料
保持永久学习的心态,将成就一个优秀的你,来 继续搞起java知识。
1You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8
这道题不算复杂,而且算是链表里经典的一道题了,掌握好链表的结构其实并不难,只是有点繁琐。
1.题目给的两个数字是用链表表示的,而且注意到链表表示出来的是它们的逆序,得出来的结果也是逆序表示的,所以不需要将原始数据做反转处理,直接按照链表从头到尾的顺序处理就行。
2.还需要注意的是给出原始数据有可能长度并不是一致的,这在代码里需要考虑到。
3.数字相加的进位处理。
4.最后一位如果还有进位,还需要在开辟一个节点。
5.算法的健壮性,存在原始数据为空的情况。
笔者在思考这道题时,为了不破坏最初的链表,用到了两个节点first和second分别表示第一个数字和第二个数字。同时用到了head和end节点来存储结果的始末,计算出来的结果直接return head就ok了。
接下来就是处理数字相加时的情况,除了两个节点的相加,还要考虑到前面数值计算时所产生的进位(add),再进行取模预算(temp%10)表示需要存储的值,以及新的进位(temp/10).
1int temp=first.val+second.val+add; int digit=temp%10; add=temp/10;
创建新的节点,与end来连接起来。
ListNode newnode=new ListNode(digit);
循环处理直到其中有链表为空,在用进位与其后续节点进行计算
1 while(first!=null){//first还有数据没处理完 int temp=first.val+add; int digit=temp%10; add=temp/10; first.val=digit; end.next=first; end=end.next; first=first.next; }
second的处理情况一样。
最后就是,链表的节点遍历完了之后add任有可能为1,需要作出判断:
1if(add==1){ //如果最后add不为0,新建一个节点(1) ListNode newnode=new ListNode(add); end.next=newnode; end=end.next; }
下面是在leetcode上Accepted的代码:
1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode head=null; ListNode end=head; ListNode first=l1; ListNode second=l2; int add=0; //进位 while(first!=null&&second!=null){ int temp=first.val+second.val+add; //进位与两个数值相加 int digit=temp%10; add=temp/10; ListNode newnode=new ListNode(digit); if(head==null){ head=newnode; end=newnode; } else { end.next=newnode; end=end.next; } first=first.next; second=second.next; } while(first!=null){//first还有数据没处理完 int temp=first.val+add; int digit=temp%10; add=temp/10; first.val=digit; end.next=first; end=end.next; first=first.next; } while(second!=null){//Second还有数据没处理完 int temp=second.val+add; int digit=temp%10; add=temp/10; second.val=digit; end.next=second; end=end.next; second=second.next; } if(add==1){ //如果最后add不为0,新建一个节点(1) ListNode newnode=new ListNode(add); end.next=newnode; end=end.next; } return head; } }
JAVAleetcode链表Add-Two-Nu
因为水平有限,难免有疏忽或者不准确的地方,希望大家能够直接指出来,我会及时改正。一切为了知识的分享。
后续会有更多的精彩的内容分享给大家。