[Algorithm] LeetCode #2 - Add Two Numbers
개요
LeetCode #2, Add Two Numbers 문제를 풀어봅니다.
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 contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0] Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]
Constraints:
- The number of nodes in each linked list is in the range
[1, 100]. 0 <= Node.val <= 9- It is guaranteed that the list represents a number that does not have leading zeros.
연결 리스트를 각각 뒤집고 더해서 숫자를 만들고 만들어진 숫자를 다시 뒤집고 뒤집은 것을 연결 리스트로 돌려주면 됩니다.
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# reverse linked list
def reverseList(self, head: ListNode) -> ListNode:
node, prev = head, None
while node:
next, node.next = node.next, prev
prev, node = node, next
return prev
# linked list to python list
def toList(self, node: ListNode) -> List:
python_list = []
while node:
python_list.append(node.val)
node = node.next
return python_list
# python list to linked list (+ reversed)
def toReversedLinkedList(self, result: str) -> ListNode:
# ListNode prev
prev = None
for r in result:
node = ListNode(r)
node.next = prev
prev = node
return node
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
a = self.toList(self.reverseList(l1))
b = self.toList(self.reverseList(l2))
resultStr = int(''.join(str(e) for e in a)) + \
int(''.join(str(e) for e in b))
return self.toReversedLinkedList(str(resultStr))
