[LEET CODE] 2. Add Two Numbers ( 숫자형 리스트 병합하기)

# Problem

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

 

# My Answer

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        node = l1
        carry = ListNode(0)
        while l1 and l2:
            l1.val = l1.val + l2.val + carry.val 
            if l1.val >=10: # 더한 값이 10이 넘어가면
                carry.next = ListNode(1)
                l1.val = l1.val-10
            else:
                carry.next = ListNode(0)
                
            # l1 이나 l2 중 하나만 더 긴 경우 나머지 0으로 채워줌
            if l1.next is not None and l2.next is None:
                l2.next=ListNode(0)
            if l1.next is None and l2.next is not None:
                l1.next=ListNode(0)
            
            # 마지막에 받아 올려야 할 값이 있을 때 l1에 연결해주기 위해서
            if l1.next is None and l2.next is None and carry.next.val !=0:
                l1.next = ListNode(0)
                
            l1 = l1.next
            l2 = l2.next
            carry = carry.next
            
        # 마지막에 받아 올려야 할 값이 있을 때   
        if carry.val !=0:
            l1.val = carry.val
        
        return node

 

# Solution 1 - 자료형 변환

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


class Solution:
    # 연결 리스트 뒤집기
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None

        while node:
            next, node.next = node.next, prev
            prev, node = node, next

        return prev

    # 연결 리스트를 파이썬 리스트로 변환
    def toList(self, node: ListNode) -> List:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        return list

    # 파이썬 리스트를 연결 리스트로 변환
    def toReversedLinkedList(self, result: str) -> ListNode:
        prev: ListNode = 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))

숫자로 변환하여 계산 후 다시 연결리스트로 만든다

 

# Solution 2 - 전가산기 (Full Adder) 구현

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


class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        root = head = ListNode(0)

        carry = 0
        while l1 or l2 or carry:
            sum = 0
            # 두 입력값의 합 계산
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2:
                sum += l2.val
                l2 = l2.next

            # 몫(자리올림수)과 나머지(값) 계산
            carry, val = divmod(sum + carry, 10)
            head.next = ListNode(val)
            head = head.next

        return root.next # 첫 노드에 0이 들어있음

자리마다 정수형으로 계산하고 연결리스트에 넣어준다.

---

# 숫자형 리스트를 단일 값으로 병합하기

 

1) join 활용

a = [1,2,3,4,5]

 ''.join( str(e) for e in a )

''.join(map(str,a))

 

2) functools - 고계함수(함수를 다루는 함수)를 지원하는 함수형 언어 모듈 -리트코드에 기본적으로 import 

a = [1,2,3,4,5]

functools.reduce (lambda x,y : 10* x + y, a, 0)

> 12345

reduce :  두 인수의 함수를 누적 적용

>>(((10+2)*10+3)*10+4)*10+5

 

3) operator 모듈 활용

import operator import add, mul

functools.reduce(add,[1,2,3,4,5])

>15