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或者是链表2.

可以看到, 第一种思路要相对多用一些空间. 第二种思路,比较省空间(但是实际上也可以忽略不计了).两个方法的的复杂度都是O(n).

这里只写第一种方法: 代码十分简单!

 public class Solution {  
   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
     if (l1 == null) return l2;  
     if (l2 == null) return l1;  
     ListNode p1=l1, p2=l2;  
     ListNode newHead = new ListNode(0);  
     ListNode p3 = newHead;  
     int carry = 0;  
     while (p1 != null || p2 != null) {  
       if (p1 != null) {  
         carry += p1.val;    
         p1 = p1.next;  
       }  
       if (p2 != null) {  
         carry += p2.val;  
         p2 = p2.next;  
       }  
       ListNode next = new ListNode(carry % 10);  
       p3.next = next;  
       p3 = p3.next;  
       carry = carry / 10;  
     }  
     if (carry != 0) {  
       p3.next = new ListNode(carry);  
     }  
     return newHead.next;  
   }  
 }