[leetcode]Add Two Numbers

又是一篇漏网之鱼，请大家移步新博文地址：[leetcode]Add Two Numbers

 

Add Two Numbers

You 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：

将两个因数转换成整型，求出和，再将和转换为链表形式

【注意】这个int类型会溢出，严格来说，long也会溢出，因此是不严谨的。

代码如下：

public class Solution {  
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            return num2List( getNum(l1)  + getNum(l2));    
        }
        private long getNum(ListNode l){
            if(l == null) return 0;
            long num = 0;
            long length = 0;
            while( l != null){
                num += Math.pow(10,length) * l.val;
                length++;
                l = l.next;
            }
            return num;
        }
        private ListNode num2List(long num){
            ListNode hhead = new ListNode(0);
            ListNode tail = hhead;
            if(num == 0) return hhead;
            while(num != 0){
                ListNode tem = new ListNode((int)(num % 10));
                tail.next = tem;
                tail = tail.next;
                num /= 10;
            }
            return hhead.next;
        }
}

 

 

思路2：

直接在两个list中进行加和操作。模拟加法。

 1 public class Solution {
 2     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 3         if(l1 == null) return l2;
 4         if(l2 == null) return l1;
 5         int l1Length = getLength(l1),l2Length = getLength(l2);
 6         if(l1Length > l2Length) return addTwoNumbers(l2, l1);
 7         ListNode l2Pointer = l2;
 8         ListNode l1Pointer = l1;
 9         while(l2Pointer != null){
10             l2Pointer.val = l2Pointer.val + ((l1Pointer == null) ? 0 : l1Pointer.val);
11             if(l2Pointer.val > 9){
12                 l2Pointer.val -= 10 ;
13                 if(l2Pointer.next == null){
14                     ListNode tail = new ListNode(1);
15                     l2Pointer.next = tail;
16                     break;
17                 }
18                 l2Pointer.next.val++;
19             }
20             l2Pointer = l2Pointer.next;
21             if(l1Pointer != null)l1Pointer = l1Pointer.next;
22         }
23         return l2;
24     }
25     private int getLength(ListNode list){
26         int length = 0;
27         while(list != null){
28             length++;
29             list = list.next;
30         }
31         return length;
32     }
33 }