leetcode每日一题(2020.10.04) 2. 两数相加

2. 两数相加(中等)

安安题解 过了99.81%

思路：先把每个链表表示的整数算出来，把这两个整数加起来，再去把这个整数表示成链表的形式 但是两数相加就要考虑大数存储的问题，所有最后一个大数的案例就通过不了 (官解)遍历链表，只加某一位的值，创建新节点。这样就不会存在大数存储的问题，就可以完美解决

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ /* 思路：先把每个链表表示的整数算出来，把这两个整数加起来，再去把这个整数表示成链表的形式 但是两数相加就要考虑大数存储的问题，所有最后一个大数的案例就通过不了 (官解)遍历链表，只加某一位的值，创建新节点。这样就不会存在大数存储的问题，就可以完美解决 这个案例告诉我们要使用long [9] [1,9,9,9,9,9,9,9,9,9] 这个案例通过不了 [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1] [5,6,4] */ //2020.10.4 anan class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { long sum = helper(l1) + helper(l2); return createList(sum); } public long helper(ListNode l){ if(l == null){ return 0; } StringBuilder sb = new StringBuilder(); ListNode p = l; while(p != null){ sb.insert(0, p.val); p = p.next; } //System.out.println(Long.parseLong(sb.toString())); return Long.parseLong(sb.toString()); } public ListNode createList(long sum){ StringBuilder sb = new StringBuilder(Long.toString(sum)).reverse(); String str = sb.toString(); char[] chars = str.toCharArray(); ListNode dummy = new ListNode(); ListNode p = dummy; for(char ch : chars){ ListNode s = new ListNode(ch-'0'); p.next = s; p = p.next; } return dummy.next; } }

官解：不存储，边遍历，边建新节点

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int carry = 0; ListNode p = l1; ListNode q = l2; ListNode dummy = new ListNode(); ListNode r = dummy; while(p != null || q != null){ int sum = (p==null ? 0 : p.val)+(q==null ? 0 : q.val)+carry; carry = (sum >= 10 ? 1 : 0); r.next = new ListNode(sum%10); r = r.next; if(p != null) p = p.next; if(q != null) q = q.next; } if(carry == 1){ r.next = new ListNode(carry); } return dummy.next; } }