2. 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

链接: http://leetcode.com/problems/add-two-numbers/

题解：

单链表的操作，要注意链表为空时的判断。这里为什么说Space Complexity = O(1)呢，因为我记得在哪个post了看了1337coder的话，说生成的结果不考虑在Space Complexity，我们只考虑过程中我们使用了多少额外的空间。这里每次我们只生成一个新的node，所以应该可以算作O(1)。

Time Complexity - O(n)，Space Complexity - O(1)。

/**
 * 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;
        ListNode result = new ListNode(-1);
        ListNode node = result;
        int carry = 0;
        
        while(l1 != null || l2 != null){
            int val1 = l1 == null ? 0 : l1.val;
            int val2 = l2 == null ? 0 : l2.val;
            node.next = new ListNode((val1 + val2 + carry) % 10);
            carry = val1 + val2 + carry >= 10 ? 1 : 0;
            if(l1 != null)
                l1 = l1.next;
            if(l2 != null)
                l2 = l2.next;
            node = node.next;
        }
        
        if(carry == 1)
            node.next = new ListNode(1);
        return result.next;
    }
}

二刷:

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(-1);
        ListNode node = res;
        int carry = 0;
        
        while (l1 != null || l2 != null) {
            int l1Val = (l1 != null) ? l1.val : 0;
            int l2Val = (l2 != null) ? l2.val : 0;
            int newVal = (l1Val + l2Val + carry) % 10;
            carry = (l1Val + l2Val + carry) >= 10 ? 1 : 0;
            node.next = new ListNode(newVal);
            node = node.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        
        if (carry == 1) {
            node.next = new ListNode(1);
        }
        
        return res.next;
    }
}

Python:

Python还是用得Java的写法，很多小trick，小细节都还不知道，要在刷题中继续学习。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        carry = 0
        l = ListNode(-1)
        node = l
        while (l1 is not None) or (l2 is not None):
            l1_val = l1.val if l1 is not None else 0
            l2_val = l2.val if l2 is not None else 0
            node.next = ListNode((l1_val + l2_val + carry) % 10)
            carry = 1 if (l1_val + l2_val + carry) >= 10 else 0
            l1 = l1.next if l1 is not None else None
            l2 = l2.next if l2 is not None else None
            node = node.next
        if carry == 1:
            node.next = ListNode(1)
        return l.next
        
        

3刷:

Java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return null;
        }
        ListNode res = new ListNode(-1);
        ListNode node = res;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int digitL1 = 0, digitL2 = 0;
            if (l1 != null) {
                digitL1 = l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                digitL2 = l2.val;
                l2 = l2.next;
            }
            int newNum = digitL1 + digitL2 + carry;
            node.next = new ListNode(newNum % 10);
            carry = newNum >= 10 ? 1 : 0;
            node = node.next;
        }
        if (carry == 1) {
            node.next = new ListNode(1);
        }
        return res.next;
    }
}

Reference:

http://www.cnblogs.com/springfor/p/3864493.html

https://leetcode.com/discuss/51471/python-concise-solution

https://leetcode.com/discuss/25432/clear-python-code-straight-forward

https://leetcode.com/discuss/36908/python-for-the-win