리트코드 - Add Two Numbers

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

LeetCode - The World's Leading Online Programming Learning Platform

 

처음에 생각했던 풀이는 다음과 같다.

연결리스트가 테스트케이스 1번을 보면

2 -> 4 -> 3 으로 순회하고

5 -> 6 -> 4 로 순회하니까.

연결리스트의 마지막까지 순회하면서 해당 값들을 문자열로 받은 다음에, 역으로 정렬시켜주면

342, 564의 형태가 될 것이고

이 값들을 더해주면 807이 나온다.

이후 이 값을 역 순회하면서 

해당 값을 연결리스트에 더해주면 되지 않을까 생각해보았다. ( 7 -> 0 -> 8 )
그리고 연결리스트에 더해주는 반복문을 어떻게 작성하여야 할 지 아이디어가 떠오르지 않아 다음 자료를 참고했다.
https://sg-data.tistory.com/15

(07) 연결 리스트 순회

자료를 참고했을때는 head와 next로 처음에 연결 리스트를 생성하고, 연결리스트들이 각각의 node들로 이루어져 있는 형태였다.

하지만 문제에서는 ListNode들이 서로의 참조 값을 갖고 있는 형태였다.

따라서 처음에 ListNode를 생성하고 합계 문자열의 마지막 인덱스를 먼저 더해줬다. 그리고 이후 인덱스부터 역으로 순회하면서 ListNode를 추가해주도록 구현하였다.

sum_num = str(int(one) + int(two))
head = ListNode(sum_num[-1])
curr = head
for i in range(len(sum_num)-2, -1, -1):
	...

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        one = ""
        two = ""
        while l1:
            one += str(l1.val)
            l1 = l1.next if l1 else None
        while l2:
            two += str(l2.val)
            l2 = l2.next if l2 else None
        
        one = one[::-1]
        two = two[::-1]
        
        sum_num = str(int(one) + int(two))
        head = ListNode(sum_num[-1])
        curr = head
        for i in range(len(sum_num)-2, -1, -1):
            new_node = ListNode(sum_num[i])
            curr.next = new_node
            curr = new_node
    
        return head