[LeetCode] Add Two Numbers - medium level

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

 

Example

     Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

     Output: 7 -> 0 -> 8

     Explanation: 342 + 465 = 807.

 

풀이

1. 기본적으로 링크드 리스트의 자료 구조를 이해하고 있어야 하며, Doubly linked list가 아니기 때문에 가장 처음 리스트의 주소값을 가지는 노드가 필요하다.

2. 각 자리의 수를 더할 때에 4+3은 하나의 자리로 표현 가능하지만 4+7이 되면 현재의 자리를 1이 되고 10에 해당하는 값이 다음 자리로 넘어가야 하기 때문에 이를 처리하기 위한 변수가 존재해야 한다.

3. Pseudo-codes는 대략 아래와 같다.

• 현재 노드를 결과값을 반환할 리스트의 처음 노드로 초기화 한다.
• 자리수가 넘어가는 값을 표현하는 carry를 0으로 초기화 한다.
• 입력 리스트인 l1과 l2의 처음 노드를 node1, node2에 할당한다.
• l1과 l2 리스트가 마지막 노드가 될 때까지 아래를 반복한다.
  • Set x에 node1의 값을, y에 node2의 값을 할당하고 None이면 0을 반환한다.
  • sum = x + y + carry
  • carry = sum / 10
  • (sum mod 10) 의 값으로 새로운 노드를 만들어 준 후 현재 노드의 다음 노드로 연결해 준다. 그리고 현재 노드를 다음 노드로 이동한다.
  • node1과 node2를 다음 노드로 각각 이동한다.
• 만약 carry가 1을 가지고 있으면 최종 결과 리스트에 1을 가지는 새로운 노드를 추가해 준다.
• 결과값을 가지는 리스트의 다음 노드값을 반환해 준다.

4. 파이썬 코드

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

class Solution:
    def get_next(self, node):
        try:
            return node.next
        except:
            return None
        
    def get_value(self, node):
        if node == None:
            return 0
        else:
            return node.val
        
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        result = ListNode(0)
        
        cur_node = result
        node1 = l1
        node2 = l2
        carry = 0
        
        while True:            
            x = self.get_value(node1)
            y = self.get_value(node2)
            
            digit_sum = x + y + carry
            
            carry = int (digit_sum / 10)
            
            cur_node.next = ListNode(digit_sum % 10)
            
            node1 = self.get_next(node1)
            node2 = self.get_next(node2)
            
            if node1 == None and node2 == None:
                break
                
            cur_node = cur_node.next
                
        if carry > 0:
            cur_node.next  = ListNode(carry)
       
        
        return result.next

 

동일한 논리를 가져가기 위해서 노드 값 및 노드 이동을 함수로 만들어서 예외처리를 하였다.