给定两个代表非负数的链表,数字在链表中是反向存储的(链表头结点处的数字是个位数,第二个结点上的数字是十位数...),求这个两个数的和,结果也用链表表示。
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 0 -> 8
public class Solution { /** * * @param l1 ListNode类 * @param l2 ListNode类 * @return ListNode类 */ public ListNode addTwoNumbers (ListNode l1, ListNode l2) { // write code here ListNode h1 = l1; ListNode h2 = l2; ListNode head = new ListNode(-1); ListNode temp = head; int flag = 0; while (h1 != null || h2 != null) { int n1 = h1 == null ? 0 : h1.val; int n2 = h2 == null ? 0 : h2.val; flag = flag + n1 + n2; temp.next = new ListNode(flag % 10); flag /= 10; h1 = h1 == null ? null : h1.next; h2 = h2 == null ? null : h2.next; temp = temp.next; } if (flag != 0) {temp.next = new ListNode(flag);} return head.next; } }
/** 有题目可以知道,数字在链表中是反向存储的,那么通过栈来时线逆序输出,从而可以得到一个数字 思路: 1)将两个给出的链表逆序输出从而转换成相应的数字 2)将两个数字相加,从而得到他们的和result 3)获得result的个位、十位(各个数位上的数字),然后插入在新建链表的链表头 4)返回新建的链表 将链表逆序输出:方法①通过栈来实现(由栈先进后出的特性),这个方法并没有改变原来的链表的顺序 方法②通过链表来实现,首先遍历原来的链表,然后将其节点查在新链表的尾节点处 */ import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param l1 ListNode类 * @param l2 ListNode类 * @return ListNode类 */ public ListNode addTwoNumbers (ListNode l1, ListNode l2) { //这里将链表对应的数字定义为long类型(因为刚开始提交的时候因为出现比int的范围更大的数,所以定义为long) long num1 = getNum(l1); long num2 = getNum(l2);//调用方法,从而获得链表对应的数字 long result = num1 + num2;//获取和 return getList(result);//获得和对应的链表,并将其返回 } /** 获得两个数的和对应的链表 1)获得和对应的位数,并将其插入在链表尾 */ public ListNode getList(long sum){ long temp;//表示位数 ListNode list = new ListNode(0); if(sum == 0){//如果sum为0,那么就将返回值为0的链表 return list; } //sum不为0 while(sum != 0){ temp = sum % 10; sum /= 10; ListNode node = new ListNode((int)temp);//新建节点 //由于list是带假节点的链表,那么将从list开始遍历(无论是否链表为空,都可以,而不用判断链表是否为空) ListNode current = list; while(current.next != null){ current = current.next; } node.next = current.next; current.next = node; } ListNode list2 = list.next; return list2; } /** 获取链表中的有效节点数--通过遍历链表,从而得到 */ public int getCount(ListNode l){ int count = 0; while(l != null){ count++; l = l.next; } return count; } /** 调用方法,从而获得对应的数字---通过栈来实现其倒序输出 */ public long getNum(ListNode l){ int count = getCount(l);//获取链表的有效节点 Stack stack = new Stack(count);//新建栈 //遍历链表,从而将数字压栈 while(l != null){ stack.push(l.val); l = l.next; } //遍历栈,从而将获得链表对应的数字--当栈为空时,就退出循环遍历 long result = 0; while(!stack.isEmpty()){ result = result * 10 + stack.pop(); } return result; } } class Stack{ int[] arr; int top;//表示队头指针(栈的增删都靠队头指针实现) int maxSize;//栈的长度 public Stack(int max){ maxSize = max; arr = new int[maxSize]; top = -1;//注意队头指针不能初始化尾0,因为数组的第一个下标就是0,不利于判断是否为空 } //压栈 public void push(int value){ if(isFull()){ //如果为满,就抛出异常,表明已经满了 throw new RuntimeException("栈为满,无法插入"); } arr[++top] = value; } //出栈 public int pop(){ if(isEmpty()){ //如果为空,就抛出异常,表明为空 throw new RuntimeException("栈为空,无法出栈"); } return arr[top--]; } //判断是否为空 public boolean isEmpty(){ return (top == -1); } //判断是否为满 public boolean isFull(){ return (top == maxSize - 1); } }
public ListNode addTwoNumbers (ListNode l1, ListNode l2) { //这里将链表对应的数字定义为long类型(因为刚开始提交的时候因为出现比int的范围更大的数,所以定义为long) long num1 = getNum(l1); long num2 = getNum(l2);//调用方法,从而获得链表对应的数字 long result = num1 + num2;//获取和 return getList(result);//获得和对应的链表,并将其返回 }这里比较疑惑的是如果数字的范围比long还要大,那么可能会出错的吧,那为什么我这个代码还可以通过?
public ListNode add(ListNode head1 ,ListNode head2){ if(head1==null&&head2==null){ return null; } if(head1 ==null){ return head2; } if(head2==null){ return head1; } boolean flag = false; int i = 0; int real = 0; //这里的val值随便指定 因为我们需要的是此cur的next结点作为我们生成的链表的头结点 ListNode cur = new ListNode((head1.val+head2.val)%10); //重新生成个cur的引用 后面我们返回这个ok.next就可以了(重新生成指针引用不修改原来指针) ListNode ok = cur; //如果两个链表都不是空 while (head1!=null&&head2!=null) { //通过flag判断是否进位 if (flag){ i=1; }else { i=0; } int sum = head1.val+head2.val+i; if(sum<10){ real = sum; flag = false; } if(sum>=10){ real = sum%10; flag = true; } ListNode p = new ListNode(real); cur.next = p; cur = p; head1= head1.next; head2 = head2.next; } //如果1遍历到头但是2没到头 if(head1==null&&head2!=null){ int j = 0; while (head2!=null){ if(flag){ j = 1; }else { j = 0; } int sum = head2.val+j; if(sum<10){ real = sum; flag = false; } if(sum>=10){ real = sum%10; flag = true; } ListNode p = new ListNode(real); cur.next = p; cur = p; head2 = head2.next; } }//如果2遍历到头但是1没到头
if(head1!=null&&head2==null){ int k = 0; while (head1!=null){ if(flag){ k = 1; }else { k= 0; } int sum = head1.val+k; if(sum<10){ real = sum; flag = false; } if(sum>=10){ real = sum%10; flag = true; } ListNode p = new ListNode(real); cur.next = p; cur = p; head1 = head1.next; } }
//最后都遍历后flag还是true 如果还是true说明仍然有进位 新生成结点值为1接在后面
System.out.println(flag);
if(flag){ ListNode p = new ListNode(1); cur.next = p; cur = p; } return ok.next; }
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if(l1 == null) return l2; if(l2 == null) return l1; int sum = 0; int jinwei = 0;//用来做进位的,往右进位 ListNode p = new ListNode(-1); ListNode head = p; while(l1 != null || l2 != null || jinwei != 0) { //l1和l2直接按位加起来 if(l1 != null) { sum += l1.val; l1 = l1.next; } if(l2!=null) { sum += l2.val; l2 = l2.next; } //再把进位加上 sum += jinwei; p.next = new ListNode(sum%10); p = p.next; jinwei = sum / 10; //除以10用来下次循环进位 sum = 0; //清零等下次循环再相加 } return head.next; } }
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1 == null || l2 == null) { return null; } ListNode dummy = new ListNode(0); ListNode cur = dummy; int carry = 0; while (l1 != null || l2 != null) { int num1 = (l1 == null) ? 0 : l1.val; int num2 = (l2 == null) ? 0 : l2.val; int sum = num1 + num2 + carry; carry = sum / 10; cur.next = new ListNode(sum % 10); cur = cur.next; if (l1 != null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } } if (carry > 0) { cur.next = new ListNode(carry); } return dummy.next; } }
public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
// 先用堆栈存起来
Stack<Integer> num1 = new Stack<>();
Stack<Integer> num2 = new Stack<>();
while (l1 != null) {
num1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
num2.push(l2.val);
l2 = l2.next;
}
int carry = 0; // 表示进位
ListNode res = new ListNode(0);
while (!num1.isEmpty() && !num2.isEmpty()) {
ListNode tmp = new ListNode(num1.pop() + num2.pop() + carry);
if (tmp.val>=10) {
carry = tmp.val / 10;
tmp.val = tmp.val % 10;
} else {
carry = 0;
}
// 结果链表插入新节点
tmp.next = res.next;
res.next = tmp;
}
// 清掉num1
while (!num1.isEmpty()) {
ListNode tmp = new ListNode(num1.pop() + carry);
if (tmp.val>=10) {
carry = tmp.val / 10;
tmp.val = tmp.val % 10;
} else {
carry = 0;
}
// 结果链表插入新节点
tmp.next = res.next;
res.next = tmp;
}
// 清掉num2
while (!num2.isEmpty()) {
ListNode tmp = new ListNode(num2.pop() + carry);
if (tmp.val>=10) {
carry = tmp.val / 10;
tmp.val = tmp.val % 10;
} else {
carry = 0;
}
// 结果链表插入新节点
tmp.next = res.next;
res.next = tmp;
}
if (carry != 0) {
ListNode tmp = new ListNode(carry);
// 结果链表插入新节点
tmp.next = res.next;
res.next = tmp;
}
return res.next;
}
另外提供镜像题目的解,即链表和结果都是最高位在前的:Add Two Numbers II,思路就是借助stack来进行逆序操作
public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
// 结果链表
ListNode res = new ListNode(0);
ListNode cur = res;
int carry = 0; // 记录进位情况
while (l1 != null && l2 != null) {
ListNode tmp = new ListNode(l1.val + l2.val + carry);
if (tmp.val>=10) {
carry = tmp.val / 10;
tmp.val = tmp.val % 10;
} else {
carry = 0;
}
// 结果链表插入新节点
cur.next = tmp;
cur = cur.next;
l1 = l1.next;
l2 = l2.next;
}
// 清空num1
while (l1 != null) {
ListNode tmp = new ListNode(l1.val + carry);
if (tmp.val>=10) {
carry = tmp.val / 10;
tmp.val = tmp.val % 10;
} else {
carry = 0;
}
// 结果链表插入新节点
cur.next = tmp;
cur = cur.next;
l1 = l1.next;
}
// 清空num2
while (l2 != null) {
ListNode tmp = new ListNode(l2.val + carry);
if (tmp.val>=10) {
carry = tmp.val / 10;
tmp.val = tmp.val % 10;
} else {
carry = 0;
}
// 结果链表插入新节点
cur.next = tmp;
cur = cur.next;
l2 = l2.next;
}
// 清掉carry
if (carry != 0) {
ListNode tmp = new ListNode(carry);
// 结果链表插入新节点
cur.next = tmp;
cur = cur.next;
}
return res.next;
}
参考代码: class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if(l1==null) return l2; if(l2==null) return l1; ListNode head = new ListNode(0); ListNode p = head; int tmp = 0; while(l1!=null || l2!=null || tmp!=0){ if(l1!=null){ tmp += l1.val; l1 = l1.next; } if(l2!=null){ tmp += l2.val; l2 = l2.next; } p.next = new ListNode(tmp%10); p = p.next; tmp = tmp/10; } return head.next; } }
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int carry = 0; ListNode res = new ListNode(0); ListNode tail = res; while(!(l1 == null && l2 == null && carry == 0)){ int x = l1 != null ? l1.val : 0; int y = l2 != null ? l2.val : 0; int sum = x + y + carry; carry = sum / 10; ListNode newNode = new ListNode(sum % 10); tail.next = newNode; tail = newNode; if(l1 != null) l1 = l1.next; if(l2 != null) l2 = l2.next; } return res.next; } }
public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode c1 = l1; ListNode c2 = l2; ListNode sentinel = new ListNode(0); ListNode d = sentinel; int sum = 0; while (c1 != null || c2 != null) { //模拟加法算表 sum /= 10; //保留进位 if (c1 != null) { sum += c1.val; c1 = c1.next; } if (c2 != null) { sum += c2.val; c2 = c2.next; } d.next = new ListNode(sum % 10); //个位数字追加 d = d.next; } if (sum / 10 == 1) //两个数相加,进位只可能是1 d.next = new ListNode(1); return sentinel.next; } }
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int carry=0; ListNode head=new ListNode(0); ListNode cur=head; while(l1!=null&&l2!=null){ cur.next=new ListNode((l1.val+l2.val+carry)%10); cur=cur.next; carry=(l1.val+l2.val+carry)/10; l1=l1.next; l2=l2.next; } while(l1!=null){ cur.next=new ListNode((l1.val+carry)%10); cur=cur.next; carry=(l1.val+carry)/10; l1=l1.next; } while(l2!=null){ cur.next=new ListNode((l2.val+carry)%10); cur=cur.next; carry=(l2.val+carry)/10; l2=l2.next; } if(carry!=0) cur.next=new ListNode(carry); return head.next; } }
Two things to make the code simple:
Let me know if there is something wrong. Thanks.
public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode prev = new ListNode(0); ListNode head = prev; int carry = 0; while (l1 != null || l2 != null || carry != 0) { ListNode cur = new ListNode(0); int sum = ((l2 == null) ? 0 : l2.val) + ((l1 == null) ? 0 : l1.val) + carry; cur.val = sum % 10; carry = sum / 10; prev.next = cur; prev = cur; l1 = (l1 == null) ? l1 : l1.next; l2 = (l2 == null) ? l2 : l2.next; } return head.next; } }
import java.math.BigDecimal; public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { l2 = reverse(l2); l1 = reverse(l1); String s1 = "", s2 = ""; while (l1 != null) { s1 += l1.val; l1 = l1.next; } while (l2 != null) { s2 += l2.val; l2 = l2.next; } String sum = new BigDecimal(s1).add(new BigDecimal(s2)).toString(); ListNode dummy = new ListNode(0), p = dummy; for (int i = 0; i < sum.length(); i ++ ) { p.next = new ListNode(Integer.valueOf(sum.charAt(i) - '0')); p = p.next; } return reverse(dummy.next); } public static ListNode reverse(ListNode head) { if(head == null || head.next == null) return head; ListNode pre = head, cur = head.next, temp; head.next = null; while (cur != null) { temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; } }