leetcode 2. Add Two Numbers

Seawolf

1. You are given two non-empty linked lists representing two non-negative integers. 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.
   
2. 
   
3. You may assume the two numbers do not contain any leading zero, except the number 0 itself.
   
4. 
   
5. Example:
   
6. 
   
7. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
   
8. Output: 7 -> 0 -> 8
   
9. Explanation: 342 + 465 = 807.

复制代码

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) { val = x; }
   
7. * }
   
8. */
   
9. 
   
10. import java.math.BigInteger;
    
11. 
    
12. class Solution {
    
13.    
    
14.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
15.         
    
16.         ListNode result =  new ListNode(0);
    
17.         
    
18.         ListNode head = result;
    
19.         
    
20.         BigInteger x , y;
    
21.         
    
22.         if(l1 == null && l2 == null){
    
23.             
    
24.             return null;
    
25.         }
    
26.         
    
27.         if(l1 == null){
    
28.             
    
29.             return l2;
    
30.         }
    
31.         
    
32.         if(l2 == null){
    
33.             
    
34.             return l1;
    
35.         }
    
36.         
    
37.         
    
38.         x = new BigInteger(reverse(get_string(l1)));
    
39.         y = new BigInteger(reverse(get_string(l2)));
    
40.         
    
41.         x = x.add(y);
    
42.         
    
43.         String a = reverse(x.toString());
    
44.         
    
45.         int len = a.length();
    
46.         
    
47.         for(int i = 0; i< len; i++){
    
48.             
    
49.             Integer it = new Integer(a.substring(i,i+1));
    
50.             
    
51.             result.next = new ListNode(it.intValue());
    
52.             
    
53.             result = result.next;
    
54.         }
    
55.         
    
56.         return head.next;
    
57.         
    
58.     }
    
59.    
    
60.     public String get_string(ListNode l){
    
61.         
    
62.         String re = "";
    
63.         
    
64.         while(l != null){
    
65.             
    
66.             re = re + l.val;
    
67.             
    
68.             l = l.next;
    
69.         }
    
70.         
    
71.         return re;
    
72.     }
    
73.    
    
74.     public String reverse(String str){
    
75.         
    
76.         String re = "";
    
77.         
    
78.         int len = str.length();
    
79.         
    
80.         for(int i = 0; i< len; i++){
    
81.             
    
82.             re = str.substring(i,i+1) + re;
    
83.         }
    
84.         
    
85.         return re;
    
86.     }
    
87.    
    
88. }

复制代码

这个code 虽然可以通过，但是效率太低了，继续优化代码.

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) { val = x; }
   
7. * }
   
8. */
   
9. 
   
10. class Solution {
    
11.    
    
12.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
13.         
    
14.         ListNode result = new ListNode(0);
    
15.         
    
16.         ListNode l = l1, j = l2, cur = result;
    
17.         
    
18.         int digit = 0;
    
19.         
    
20.         while(l != null || j != null){
    
21.             
    
22.             int x = (l != null) ? l.val : 0;
    
23.             
    
24.             int y = (j != null) ? j.val : 0;
    
25.             
    
26.             int sum = digit + x + y;
    
27.             
    
28.             digit = sum / 10;
    
29.             
    
30.             ListNode nex = new ListNode(sum % 10);
    
31.             
    
32.             cur.next = nex;
    
33.             
    
34.             cur = cur.next;
    
35.             
    
36.             if(l != null){
    
37.                
    
38.                 l = l.next;
    
39.             }
    
40.             
    
41.             if(j != null){
    
42.                
    
43.                 j = j.next;
    
44.             }
    
45.         }
    
46.         
    
47.         if(digit > 0 ){
    
48.             
    
49.             ListNode nex = new ListNode(digit);
    
50.             
    
51.             cur.next = nex;
    
52.             
    
53.             cur = cur.next;
    
54.         }
    
55.         
    
56.         return result.next;
    
57.     }
    
58.    
    
59. }

复制代码

nice job!