[Leetcode 2] - Add Two Numbers w/ Python

문제

 

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.

 

 

두개의 연결 리스트가 주어졌을때 노드는 숫자의 각 자리를 표현한다.

리스트 1의 숫자는 342라고 가정하면 반대로 돌려서 243: 2 -> 4 -> 3

똑같이 리스트 2는 465: 5 -> 6 -> 4

이럴때 342 + 465 = 807임으로 7->0->8 리스트를 아웃풋 해야된다

 

 

https://leetcode.com/problems/add-two-numbers/description/

 

 

---

 

 

예시

 

 

예시 1

예시 1

 

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

 

예시 2

Input: l1 = [0], l2 = [0]
Output: [0]

 

예시 3

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

 

 

---

 

풀이

 

첫번째 풀이는 모든 단계를 하나하나씩 구현

1. 새로운 노드를 만든다

2. 기존 노드를 기억한다 (마지막 자리를 위해)

3. 리스트 값을 더한 다음 carry on이 있는지 확인한다

4. 리스트 한개가 더 이상 값이 없으면 각자 list1, list2를 체크

5. 마지막 값이 0이면 노드를 삭제한다

 

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        sumList = ListNode(val = 0) # 노드 만들기
        prev = sumList # 현재 노드 기억
        ans = sumList # 헤드 기억
        
        while l1 and l2: # 리스트가 둘다 값이 있을때
            nextNode = ListNode(val = 0) # 노드 만들고
            prev = sumList # 기억하고

            if l1.val + l2.val + sumList.val > 9: # 10을 넘기는지 확인
                nextNode.val = 1 # carry on 기억
			
            # 노드에 값들을 설정하고 다음 노드로 넘어가기
            sumList.val = (l1.val + l2.val + sumList.val) % 10 
            sumList.next = nextNode
            sumList = sumList.next
            l1, l2 = l1.next, l2.next
        
        while l1: # 똑같이 l1이 남아 있을때
            nextNode = ListNode(val = 0)
            prev = sumList

            if l1.val + sumList.val > 9:
                nextNode.val = 1

            sumList.val = (l1.val + sumList.val) % 10
            sumList.next = nextNode
            sumList = sumList.next
            l1 = l1.next
        
        while l2: # l2에 값이 남아 있을때
            nextNode = ListNode(val = 0)
            prev = sumList

            if l2.val + sumList.val > 9:
                nextNode.val = 1

            sumList.val = (l2.val + sumList.val) % 10
            sumList.next = nextNode
            sumList = sumList.next
            l2 = l2.next
        
        if prev.next.val == 0: # 마지막 노드가 0이라면 삭제
            prev.next = None

        return ans # 헤드 리턴

 

 

나쁘지 않지만 흠...

 

풀이에 반복적인 부분이 많아서 수정을 하기로 했다

 

---

 

1. carry on 구하기 방식을 수정

2. l1, l2 합치고 계산하는 방식 수정

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        point = ListNode()
        curr = point
        carry = 0
        
	# carry가 들어가는 이유는 마지막 케이스 확인을 위해 
        # 마지막에 5 + 7 을 했다고 가정하면 l1, l2는 더 이상 값이 없기 때문에 마지막 1을 추가 못함
        while l1 or l2 or carry:
            one = l1.val if l1 else 0
            two = l2.val if l2 else 0

            total = one + two + carry
            carry = total // 10
            total = total % 10
            curr.next = ListNode(total)

            curr = curr.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        
        return point.next

 

 

편안...