<reponame>JulyKikuAkita/PythonPrac
__source__ = 'https://github.com/kamyu104/LeetCode/blob/master/Python/add-two-numbers-ii.py'
# https://leetcode.com/problems/add-two-numbers-ii/#/description
# Time:  O(m + n)
# Space: O(m + n)
#
# Description: 445. Add Two Numbers II
#
# You are given two linked lists representing two non-negative numbers.
# The most significant digit comes first and each of their nodes contain a single digit.
# Add the two numbers and return it as a linked list.
#
# You may assume the two numbers do not contain any leading zero, except the number 0 itself.
#
# Follow up:
# What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
#
# Example:
#
# Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
# Output: 7 -> 8 -> 0 -> 7

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
#  Microsoft Bloomberg
# Hide Tags Linked List
# Hide Similar Problems (M) Add Two Numbers

import unittest
# 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
        """
        stk1, stk2 = [], []
        while l1:
            stk1.append(l1.val)
            l1 = l1.next
        while l2:
            stk2.append(l2.val)
            l2 = l2.next

        prev, head = None, None
        sum = 0
        while stk1 or stk2:
            sum /= 10
            if stk1:
                sum += stk1.pop()
            if stk2:
                sum += stk2.pop()

            head = ListNode(sum % 10)
            head.next = prev
            prev = head

        if sum >= 10:
            head = ListNode(sum / 10)
            head.next = prev

        return head

    def addTwoNumbers2(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        x1, x2 = 0, 0
        while l1:
            x1 = x1*10+l1.val
            l1 = l1.next
        while l2:
            x2 = x2*10+l2.val
            l2 = l2.next
        x = x1 + x2

        head = ListNode(0)
        if x == 0: return head
        while x:
            v, x = x%10, x//10
            head.next, head.next.next = ListNode(v), head.next

        return head.next

class TestMethods(unittest.TestCase):
    def test_Local(self):
        self.assertEqual(1, 1)


if __name__ == '__main__':
    unittest.main()

Java = '''
#Thought:
#

# 29ms 76.31%
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();

        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }

        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }

        int sum = 0;
        ListNode node = new ListNode(0);
        while(!s1.isEmpty() || !s2.isEmpty()) {
            if (!s1.isEmpty()) sum += s1.pop();
            if (!s2.isEmpty()) sum += s2.pop();
            node.val = sum % 10;
            ListNode head = new ListNode(sum / 10);
            head.next = node;
            node = head;
            sum /= 10;
        }
        return node.val == 0 ? node.next : node;
    }
}
'''
__source__ = 'https://github.com/kamyu104/LeetCode/blob/master/Python/add-two-numbers-ii.py'
# https://leetcode.com/problems/add-two-numbers-ii/#/description
# Time:  O(m + n)
# Space: O(m + n)
#
# Description: 445. Add Two Numbers II
#
# You are given two linked lists representing two non-negative numbers.
# The most significant digit comes first and each of their nodes contain a single digit.
# Add the two numbers and return it as a linked list.
#
# You may assume the two numbers do not contain any leading zero, except the number 0 itself.
#
# Follow up:
# What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
#
# Example:
#
# Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
# Output: 7 -> 8 -> 0 -> 7

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
#  Microsoft Bloomberg
# Hide Tags Linked List
# Hide Similar Problems (M) Add Two Numbers

import unittest
# 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
        """
        stk1, stk2 = [], []
        while l1:
            stk1.append(l1.val)
            l1 = l1.next
        while l2:
            stk2.append(l2.val)
            l2 = l2.next

        prev, head = None, None
        sum = 0
        while stk1 or stk2:
            sum /= 10
            if stk1:
                sum += stk1.pop()
            if stk2:
                sum += stk2.pop()

            head = ListNode(sum % 10)
            head.next = prev
            prev = head

        if sum >= 10:
            head = ListNode(sum / 10)
            head.next = prev

        return head

    def addTwoNumbers2(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        x1, x2 = 0, 0
        while l1:
            x1 = x1*10+l1.val
            l1 = l1.next
        while l2:
            x2 = x2*10+l2.val
            l2 = l2.next
        x = x1 + x2

        head = ListNode(0)
        if x == 0: return head
        while x:
            v, x = x%10, x//10
            head.next, head.next.next = ListNode(v), head.next

        return head.next

class TestMethods(unittest.TestCase):
    def test_Local(self):
        self.assertEqual(1, 1)


if __name__ == '__main__':
    unittest.main()

Java = '''
#Thought:
#

# 29ms 76.31%
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();

        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }

        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }

        int sum = 0;
        ListNode node = new ListNode(0);
        while(!s1.isEmpty() || !s2.isEmpty()) {
            if (!s1.isEmpty()) sum += s1.pop();
            if (!s2.isEmpty()) sum += s2.pop();
            node.val = sum % 10;
            ListNode head = new ListNode(sum / 10);
            head.next = node;
            node = head;
            sum /= 10;
        }
        return node.val == 0 ? node.next : node;
    }
}
'''
# https://leetcode.com/problems/add-two-numbers-ii/#/description # Time:  O(m + n) # Space: O(m + n) # # Description: 445. Add Two Numbers II # # You are given two linked lists representing two non-negative numbers. # The most significant digit comes first and each of their nodes contain a single digit. # Add the two numbers and return it as a linked list. # # You may assume the two numbers do not contain any leading zero, except the number 0 itself. # # Follow up: # What if you cannot modify the input lists? In other words, reversing the lists is not allowed. # # Example: # # Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) # Output: 7 -> 8 -> 0 -> 7 # Definition for singly-linked list. # class ListNode(object): #     def __init__(self, x): #         self.val = x #         self.next = None # #  Microsoft Bloomberg # Hide Tags Linked List # Hide Similar Problems (M) Add Two Numbers # Definition for singly-linked list. :type l1: ListNode         :type l2: ListNode         :rtype: ListNode :type l1: ListNode         :type l2: ListNode         :rtype: ListNode #Thought: #  # 29ms 76.31% class Solution {     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {         Stack<Integer> s1 = new Stack<Integer>();         Stack<Integer> s2 = new Stack<Integer>();          while (l1 != null) {             s1.push(l1.val);             l1 = l1.next;         }          while (l2 != null) {             s2.push(l2.val);             l2 = l2.next;         }          int sum = 0;         ListNode node = new ListNode(0);         while(!s1.isEmpty() || !s2.isEmpty()) {             if (!s1.isEmpty()) sum += s1.pop();             if (!s2.isEmpty()) sum += s2.pop();             node.val = sum % 10;             ListNode head = new ListNode(sum / 10);             head.next = node;             node = head;             sum /= 10;         }         return node.val == 0 ? node.next : node;     } }