[leetcode/python] 2번 Add Two Numbers

https://leetcode.com/problems/add-two-numbers/submissions/932885917/

Add Two Numbers - LeetCode

 

문제 요약 : 두 연결 리스트를 각 노드마다 값을 더해서 새로운 연결 리스트 반환

- 두 값의 합이 10을 넘어가면 올림 해줘야 한다!

 

로직은 다음과 같다.

1. 두 연결 리스트를 돌면서, (둘 다 값이 모두 있을 때) 합산해준다. 올림은 ten 변수로 계산한다.

2. 남은 연결 리스트가 있다면 추가적으로 돌면서 합산해준다.

3. 마지막에도 올림 변수 ten에 값이 있다면 노드를 추가해 준다.

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 올림을 담는 변수
        ten = 0
        result = ListNode(0)
        cur = result

		# 둘다 있을 경우 합산
        while l1 and l2:
            sum = l1.val + l2.val + ten
            ten = 0

            if sum >= 10:
                cur.next = ListNode(sum - 10)
                ten = 1
            else:
                cur.next = ListNode(sum)

            l1, l2, cur = l1.next, l2.next, cur.next
            
        temp = l1 or l2
    
    	# 리스트가 남았다면
        while temp:
            sum = temp.val + ten
            ten = 0
            if sum >= 10:
                cur.next = ListNode(sum - 10)
                ten = 1
            else:
                cur.next = ListNode(sum)

            temp, cur = temp.next, cur.next

		# 마지막에 올림이 남았으면 추가
        if ten == 1:
            cur.next = ListNode(1)

        return result.next

시간복잡도 : O(n)

 

개선한다면...

- 올림 변수명을 carry로 하면 더 낫겠다.

- 연결 리스트를 둘 다 있을 때와 아닐 때, 이렇게 두번 돌지 않고 while문을 한번만 쓰면서 if 조건문으로 값이 있는 노드만 합산해주면 더 깔끔해지겠다.

while l1 or l2:
    if l1:
      sum에 합산
    if l2:
      sum에 합산